Жадные алгоритмы аппроксимации: различия между версиями

Жадные алгоритмы аппроксимации (посмотреть исходный код)

3 байта добавлено , 24 апреля 2015

м

4430

правок

@@ Строка 168: / Строка 168: @@
-Более того, поскольку–q является субмодулярной,
+Более того, поскольку –q является субмодулярной, <math>\Delta_{y_j} q(C_i) - \Delta_{y_j} q(C_i \cup C^*_{j - 1}) \le 0</math>.
-Таким образом,
-где C* = ;. Но, согласно жадному правилу выбора xi + 1, должно иметь место
-f(Ci) -/(Q+1) > f(Ci) -/(C, U yjg)
-Теперь можно провести корректный анализ жадного алгоритма A для MCDS [4]. Согласно лемме 3
+Таким образом, <math>\Delta_{y_j} f(C_i) - \Delta_{y_j} f(C_i \cup C^*_{j - 1}) \le 1</math>.
+Теперь можно провести корректный анализ жадного алгоритма A для MCDS [4]. Согласно лемме 3,