Изменения

Перейти к: навигация, поиск
Нахождение коэффициента аппроксимации множества решения максимизируюшего гиперобъем
<tex>MINCON(X) \leq \frac{(x_n - x_1)}{\sum\limits_{i=2}^{n-1}1/b_i}</tex>
Так как среднее гармоническое меньше чем среднее арифметическоене больше среднего арифметического:
<tex> \frac{n - 2}{\sum\limits_{i=2}^{n-1}1/b_i} \leq \frac{\sum\limits_{i=2}^{n-1}1/b_i}{n - 2}</tex>
|statement=Пусть <tex>f \in \mathbb{F}, n > 4</tex>. Любое множество решение <tex>\{x_1, x_2, \ldots, x_d\} \in X_{HYP}^f </tex> достигает <tex>1 + \frac{ \sqrt{A/a} + \sqrt{B/b} }{n - 4}</tex> мультипликативной аппроксимации всех внутренних точек.
|proof=
Доказательство производится от противного, принимая предположение, что существует такой <tex> x</tex>, для которого бы не не выполнялось условие аппроксимации при данном коэффициенте.
}}
Совместно Теоремы теоремы 1 и 2 приводят к следующим следствиям:
'''Следствие:''' <tex>\alpha_{opt} = 1 + \Theta(1/n)</tex>
Пусть <tex>f \in \mathbb{F}, n > 4</tex>. И , и <tex> R = (R_x, R_y) \leq (0, 0) </tex> является точкой отсчета. Тогда:
<tex> \lambda_{HYP} \leq 1 + \max{ \frac{ \sqrt{A/a} + \sqrt{B/b} }{n - 4}}{\frac{A}{(a - R_x)(n - 2)^2}}{\frac{B}{(b - R_y)(n - 2)^2}}</tex>
или <tex>R_x \leq - \sqrt{Aa}/n, R_y \leq - \sqrt{Bb}/n</tex>,
тогда:выполняется следующее неравенство
<tex> \alpha _{HYP} \leq 1 + \frac{ \sqrt{ \frac{A}{a}} + \sqrt{ \frac{B}{b}}}{n - 4}</tex> = <math> 1 + \Theta ( \frac{1}{n}) </math>,
то есть: <tex> \alpha _{HYP} </tex> = <math> 1 + \Theta ( \frac{1}{n}) </math>,  что и требовалось доказать.
=Примечание=
Анонимный участник

Навигация