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

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

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

4430

правок

@@ Строка 28: / Строка 28: @@
-где n = |V|. Заметим, что 1 - 1/ opt < е~11оР(. Следовательно, f(Ci)-2<(n-2)e-il°Pt : Выберем такое значение i, что f(Ci) > opt + 2 > f(Ci+1). Тогда opt < (п-2)е-"°Р( и
+где <math>n = |V| \;</math>. Заметим, что <math>1 - 1/ opt \le  e^{- 1/opt} </math>. Следовательно, <math>f(C_i) - 2 \le (n - 2) e^{-i/opt}</math>.
-g - i < opt :
+Выберем такое значение i, что <math>f(C_i) \ge opt + 2 > f(C_{i+1})</math>. Тогда <math>opt \le (n - 2) e^{-i/opt}</math> и <math>g - i \le opt \;</math>.