64
правки
Изменения
м
→Нахождение коэффициента аппроксимации множества решения максимизируюшего гиперобъем
Пусть <tex>a_i, b_i </tex> — длины сторон соответствующего прямоугольника, тогда:
<tex> a_i \geq MinCon(X)/b_i </tex> для всех <tex>i \in [2, n - 1]</tex>
Это означает:
Применив [[#statement2|утверждение (2)]], получим:
<tex>MinCon(X) \leq (x_i - x_1)(f(x_1) - f(x_i))/(i - 2)^2 \leq x_iB/(i - 2)^2</tex> для всех <tex>i \in [3, n - 1]</tex> (2)
<tex>MinCon(X) \leq (x_n - x_{i + 1})(f(x_{i + 1}) - f(x_n))/(n - i - 2)^2 \leq A f(x_{i + 1})/(n - i - 2)^2</tex> для всех <tex>i \in [1, n - 3]</tex> (3)
Таким образом, <tex>(\alpha - 1)^2 x_i f(x_{i + 1}) < \min \{\frac{x_iB}{(i - 2)^2} ,\frac{A f(x_{i + 1})}{(n - i - 2)^2}\} \Leftrightarrow</tex> <tex>\alpha < 1 + \min \{\frac{\sqrt{x_iB}}{i - 2} ,\frac{\sqrt{A f(x_{i + 1})}}{n - i - 2}\}</tex>.
