64
правки
Изменения
→Нахождение коэффициента аппроксимации множества решения максимизируюшего гиперобъем
}}
Далее необходимо посчитать коэффициент аппроксимации для "внутренних " (<tex>x \in [x_1, x_n]</tex>) и "внешних " точек <tex>x < x_1</tex> или <tex>x > x_n</tex>.
{{УтверждениеТеорема (1)|statement=Пусть <tex>f \in \mathbb{F}, n \geq 3> 4</tex> и . Любое множество ррешение <tex>X= \left(x_1, x_2, \ldots, x_d \right) \in X X_{HYP}^f </tex>.Тогда [[http:достигает <tex>1 + \frac{ \sqrt{A/a} + \sqrt{B/neercb} }{n - 4}</tex> мультипликативной аппроксимации всех внутренних точек.ifmo.ru|proof=Доказательство производится от противного, принимая предположение, что существует такой <tex> x</wiki/indextex>, для которого бы не не выполнялось условие аппроксимации при данном коэффициенте.php?title=Сложность_задачи_вычисления_Least_Hypervolume_Contributor_и_задачи_его_аппроксимации| MINCON]] данного множество решения:}}
{{Теорема (2)|statement=Пусть <tex>f \in \mathbb{F}, n > 3</tex>. И <tex>MINCONR = (XR_x, R_y) \leq (0, 0) </tex> является точкой отсчета. Каждое множество решение <tex>(x_1, x_2, \ldots, x_d \right) \in X_{HYP}^f </tex> достигает <tex>1 + \frac{A}{(x_n a - x_1R_x)(f(x_1) n - f(x_n)2)^2}</tex> мультипликативной аппроксимации всех точек с <tex>x < x_1</tex>, и достигает <tex>1 + \frac{B}{(b - R_y)(n-2)^2}</tex>мультипликативной аппроксимации всех точек с <tex>x > x_n</tex>.
|proof=
<tex> \sum\limits_lambda_{i=2}^{n-1HYP} MINCON(x)/b_i \leq 1 + \summax{ \limits_frac{i=2}^\sqrt{n-1A/a} a_i \leq \sum+ \limits_sqrt{i=2B/b} }^{n- 4} a_i = \sum\limits_{i=2}^{n} x_i - \sum\limits_frac{i=1A}^{n-1} x_i = x_n (a - x_1 </tex> и поэтому:<tex>MINCON(XR_x) \leq \frac{(x_n n - x_12)}{\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=2B}^{n(b -1}1/b_i}{R_y)(n - 2)^2}}</tex> |proof=Преобразуя, получаем искомоеДоказательство производится c использованием ранее доказонного утверждения о MINCON.
}}
В статье [1], п. 4 приведено доказательство того, что для данного вида функций всегда существует множество решение, максимизирующее значение индикатора гиперобъема, а также устанавливает значение коэффициент аппроксимации значением: <tex>1 + \frac{ \sqrt{ \frac{A}{a}} + \sqrt{ \frac{B}{b}}}{n - 4}</tex> = <math> 1 + \Theta ( \frac{1}{n}) </math>.
