Связь между максимизацией гиперобъема и аппроксимацией Парето-фронта

Оптимальный коэффициент апроксимации для произвольного Парето-фронта из n точек ограничивается [math] 1 + \Theta (1/n) [/math]. Докажем, что он равен асимптотическому коэффициенту апроксимации для множества из n точек максимизирующих значение индикатора гиперобъема.

Рассмотрим функции вида: [math]f:[a,A] \rightarrow [b,B][/math], где [math]f[/math] убывает и [math]f(a)=B, f(A)=b[/math].. Коэффициент апроксимации монотонно убывающих функций не зависит от масштабов отрезков [math] [a,A][/math] и [math][b,B] [/math]. Так как для фиксированных констант [math] \mu , \nu [/math] функция [math] f^*:[ \mu a , \mu A ] \rightarrow [ \nu b , \nu B ][/math] и [math] f^*= \nu f(x/ \mu ) [/math] имеет тот же коэффициент аппроксимации. Однако, коэффициент аппроксимации зависит от значений [math]A/a[/math] и [math]B/b[/math].

Множество всех таких функций обозначим через [math]\mathbb{F}[/math].

Для данного класса функций множества размера [math]n[/math] имеют оптимальный аппроксимационный коэффициент: [math]1 + \frac{\log (\min ( \frac{A}{a}, \frac{B}{b}))}{n}[/math] = [math] 1 + \Theta ( \frac{1}{n}) [/math]. Верхняя граница задает нижнюю границу для коэффициента апроксимации, который может быть достигнут для любого множества решения. Докажем, что для множества максимизирующего значение индикатора гиперобъема мы можем достичь верхнюю границу [math]1 + \frac{ \sqrt{ \frac{A}{a}} + \sqrt{ \frac{B}{b}}}{n - 4}[/math] = [math] 1 + \Theta ( \frac{1}{n}) [/math], для коэффициента апроксимации.

Основные определения

Определение:

Множество [math]X^* \subseteq X[/math] называется Парето оптимальным, если: [math]\mathrm{\forall x^* \subset X^* \not \exists x \subset X : x \succ x^*}[/math], где [math] x \succ x^* [/math]([math]x[/math] доминирует [math]x^*[/math])[math] \leftrightarrow \left( \forall i \in 1 \ldots d: f_i(x) \gt f_i(x^*) \right) \bigwedge \left( \exists i \in 1 \ldots d: f_i(x) \gt f_i(x^*)\right)[/math] [math]P(X^*)[/math] - множество оптимальных по Парето решений, его также называют Парето-фронтом. Парето-фронт не может быть вычислен за полиномиальное время.

Определение:

Множество решений [math]\mathrm{X=(x_1,x_2, \ldots , x_n)}[/math] называется [math]\alpha[/math]-аппроксимацией функции [math]f \in \mathbb{F}[/math], если: [math]\mathrm{\forall x \in [a,A] \exists x_i \in X : (x \leq \alpha x_i) \bigwedge (f(x) \leq \alpha f(x_i))}[/math]

Определение:

Коэффицентом аппроксимации функции [math]f[/math] на [math]X[/math] равен: [math]\mathrm{\alpha (f, X) = inf \{\alpha | X} - \alpha[/math] аппроксимация [math]f \}[/math]

Определение:

Оптимальный коэффицент аппроксимации [math]\alpha_{opt} = \sup \limits_{f \in \mathbb{F}} \inf \limits_{x \in \mathbb{X}} \alpha (f, X)[/math]

Определение:

Индикатор называется эластичным по Парето(Pareto-compliant), если для любых двух множеств решения [math]A[/math] и [math]B[/math] значение индикатора для [math]A[/math] больше значения для [math]B[/math] тогда и только тогда, когда [math]A[/math] доминирует [math]B[/math].

Определение:

Пусть дано множество решения [math]\mathrm{X \in \mathbb{R}^d}[/math]. Пусть также множество всех решений усечено некоторой точкой [math]\mathrm{r = \left(r_1, r_2, \ldots, r_d \right)}[/math]. Тогда: [math]\mathrm{HYP\left(X\right)=VOL\left( \bigcup\limits_{\left(x_1, x_2, \ldots, x_d \right) \in X} \left[ r_1, x_1\right] \times \left[ r_2, x_2\right] \times \cdots \times \left[ r_d, x_d\right] \right)}[/math], где через [math]VOL(X)[/math] обозначена мера множества [math]X[/math] по Лебегу. Гиперобъем является единственным унарным индикатором эластичным по Парето(Pareto-compliant).