Изменения

Перейти к: навигация, поиск
Нет описания правки
Далее необходимо посчитать коэффициент аппроксимации для "внутренних" (<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 \right) \in X_{HYP}^f </tex> достигает <tex>1 + \frac{ \sqrt{A/a} + \sqrt{B/b} }{n - 4}</tex> мультипликативной аппроксимации всех внутренних точек.
|proof=
}}
{{Теорема (|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 \right) \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=
Совместно Теоремы 1 и 2 приводят к следующим следствиям:
'''Следствие:''' <tex>\alpha_{{Следствиеopt} = 1 + \Theta(1/n)</tex> |statement=Пусть <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>
|proof=
Доказательство производится c использованием ранее доказонного утверждения о MINCON.
}}
В статье ['''Следствие:''' <tex>\alpha_{opt} = 1 + \Theta(1]/n)</tex> Пусть <tex>f \in \mathbb{F}, пn > 4</tex>. 4 приведено доказательство тогоИ <tex> R = (R_x, R_y) \leq (0, что для данного вида функций всегда существует множество решение0) </tex> является точкой отсчета. Тогда если  <tex> n \geq 2 + \max{\sqrt{A/a}}{\sqrt{B/b}}</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>, что и требовалось доказать.
=Примечание=
64
правки

Навигация