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

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

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

4501

правка

@@ Строка 177: / Строка 177: @@
-Следовательно,
+Следовательно, <math>f(C_{i + 1}) - 2 - opt \le (f(C_i) - 2 + opt) \left ( 1 - \frac{1}{opt} \right ) \le (f( \empty ) - 2 - opt) \left ( 1 - \frac{1}{opt} \right )^{i + 1} = (n - 2 - opt) \left ( 1 - \frac{1}{opt} \right )^{i + 1}</math>,
-f(Ci+1) -2-opt< (f(Ci) - 2 + opt) 1 - 1 <(/(0)-2-o,f)(l--L)H
-= (n - 2 - opt) ( 1 - 1 opt
 where n = jVj. Note that 1 - 1/opt < е~11оР(. Hence,
 f(Ci) -2-opt<(n- 2)e~ilopt : Choose i such that f(Ci) > 2 • opt + 2 > f(Ci+1). Then