64
правки
Изменения
→Нахождение коэффициента аппроксимации множества решения максимизируюшего гиперобъем
==Нахождение коэффициента аппроксимации множества решения максимизируюшего гиперобъем==
{{Утверждение
|statement=Пусть <tex>f \in \mathbb{F}, n \geq 3</tex> и <tex>X= \left({x_1, x_2, \ldots, x_d \right) } \in X </tex>.
Тогда [[http://neerc.ifmo.ru/wiki/index.php?title=Сложность_задачи_вычисления_Least_Hypervolume_Contributor_и_задачи_его_аппроксимации| MINCON]] данного множество решения:
}}
Далее необходимо посчитать коэффициент аппроксимации для "внутренних" (<tex>x \in [x_1, x_n]</tex>) и "внешних" точек (<tex>x < x_1</tex> или <tex>x > x_n</tex>).
{{Теорема
|id=1
|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>, для которого бы не не выполнялось условие аппроксимации при данном коэффициенте.
{{Теорема
|id=2
|statement=Пусть <tex>f \in \mathbb{F}, n > 3</tex>. И <tex> R = (R_x, R_y) \leq (0, 0) </tex> является точкой отсчета. Каждое множество решение <tex>(\{x_1, x_2, \ldots, x_d\}) \in X_{HYP}^f </tex> достигает <tex>1 + \frac{A}{(a - R_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=
Доказательство производится c использованием ранее доказонного утверждения о MINCON.
