64
правки
Изменения
м
<tex>\forall i \in [3, n - 1]</tex> <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>\forall i \in [1, n - 3]</tex> <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)
→Нахождение коэффициента аппроксимации множества решения максимизируюшего гиперобъем
|proof=
Исходя из определения минимальный вклад в гиперобъем множества равен минимуму из всевозможных площадей прямоугольников, образующихся между точками множества-решения и их значениями. Примеры образующихся прямоугольников заштрихованы на рисунке ниже
[[Файл:Untitled2.jpg]]
Пусть <tex>a_i, b_i </tex> — длины сторон соответствующего прямоугольника, тогда:
<tex> a_i \geq MinCon(X)/b_i \forall для всех i \in [2, n - 1]</tex>
Это означает:
}}
Далее необходимо посчитать коэффициент аппроксимации для "внутренних" «внутренних» (<tex>x \in [x_1, x_n]</tex>) и "внешних" «внешних» точек (<tex>x < x_1</tex> или <tex>x > x_n</tex>).
{{Теорема
Применив [[#statement2|утверждение (2)]], получим:
Таким образом, <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>.
