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

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

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

4430

правок

@@ Строка 180: / Строка 180: @@
-где <math>n = |V| \;</math>. Заметим, что <math>1 - 1/opt \le e^{-1/opt}</math>. Таким образом,
+где <math>n = |V| \;</math>. Заметим, что <math>1 - 1/opt \le e^{-1/opt}</math>. Таким образом, <math>f(C_i) - 2 - opt \le (n - 2) e^{ -i/opt}</math>.
-f(Ci) -2-opt<(n- 2)e~ilopt : Choose i such that f(Ci) > 2 • opt + 2 > f(Ci+1). Then
+Выберем такое <math>i \;</math>, чтобы выполнялось <math>f(C_i) \ge 2 \cdot opt + 2 > f(C_{i+1})</math>. Тогда <math>opt \le (n - 2) e^{ -i/opt}</math> и <math>g - i \le 2 \cdot opt \;</math>.
-opt <{n-2)e-ilopt and
-g - i < 2 ■ opt :
-Therefore,
+Следовательно, <math>g \le 2 \cdot opt + i \le opt \left ( 2 + ln \frac {n - 2} {opt} \right ) \le opt (2 + ln \; \delta)</math>, где <math>\delta \;</math> – максимальная степень исходного графа G.
-и-2 opt
-< opt(2 +ln<5)
-g < 2 ■ opt + i < opt   2 + ln
-где S – максимальная степень исходного графа G.
 == Применение ==