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

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

362 байта добавлено , 23 апреля 2015

4551

правка

@@ Строка 133: / Строка 133: @@
-<math>f(C_i) - 2 = f(C_i) - f(C_i \cup C^*) = \sum_{j=1}^{opt} [f(C_i \cup C^*_{j - 1}) - f(C_i \cup C^*_j) ] </math>
+<math>f(C_i) - 2 = f(C_i) - f(C_i \cup C^*) = \sum_{j=1}^{opt} [f(C_i \cup C^*_{j - 1}) - f(C_i \cup C^*_j) ] </math>,
+где <math>C^*_0 = \empty \;</math>. Согласно жадному правилу выбора <math>x_i + 1 \;</math>, должно иметь место соотношение <math>f(C_i) - f(C_{i + 1}) \ge f(C_i) - f(C_i \cup \{ y_i \} )</math> для <math>j = 1, ..., opt \;</math>. Следовательно, для того, чтобы выполнялось
+<math>f(C_i) - f(C_{i + 1}) \ge \frac{f(C_i) - 2}{opt}</math>,
+должно иметь место соотношение
 (2)
-для j = 1; : : : ; opt. Следовательно, необходимо -Ayjf(Ci)=f(Ci)-f(CiU{yj}),
-чтобы выполнялось