Изменения
Нет описания правки
<tex>\mathrm{CON}(M, x) := \mathrm{HYP}(M) - \mathrm{HYP}(M \setminus x)</tex> – вклад элемента <tex>x \in M</tex> в гиперобъем.
<tex>\mathrm{MINCON}(M) := \min \limits_{x \in M} \mathrm{CON}(M, x)</tex> – минимальный вклад в гиперобъем множества. Задача MINCON – задача нахождения <tex>\mathrm{MINCON}(M)</tex>.
<tex>\mathrm{LC}(M) := \mathrm{argmin}_{x \in M} \mathrm{CON}(M, x)</tex> – least contributor, минимальный вкладчик, элемент, имеющей минимальный вклад в гиперобъем. Задача LC – задача нахождения <tex>\mathrm{LC}(M)</tex>.
<tex>\varepsilon\text{-}\mathrm{LC}(M)</tex> – элемент, имеющий вклад, отличающийся от минимального не более, чем в <tex>1 + \varepsilon</tex> раз, то есть
<tex>\mathrm{CON}(M, \varepsilon\text{-}\mathrm{LC}(M)) \le (1 + \varepsilon)\mathrm{MINCON}(M)</tex>. Задача <tex>\varepsilon</tex>-LC – задача нахождения <tex>\varepsilon\text{-}\mathrm{LC}(M)</tex>.
== Сложность задачи MINCON ==
другим, то есть <tex>C_i \nsubseteq C_j</tex> для любых <tex>i \neq j</tex>.
Для каждого <tex>A_k</tex> существуют такие <tex>x_i = a_i^k - 1</tex>, что область <tex>[x_1, x_1 + 1] \times \ldots \times [x_d, x_d + 1] \times [1, 2^d + 2]</tex> уникально покрывается только
элементом <tex>A_k</tex>, что означается, что <tex>\mathrm{CON}(M, A_k) > 2^d</tex> для любого <tex>k</tex>. Так как объем <tex>B</tex> составляется составляет лишь <tex>2^d</tex>, то
именно <tex>B</tex> будет являться минимальным вкладчиком.
|proof=
Для докозательства доказательства этой теоремы сведем задачу MINCON к задаче <tex>\varepsilon</tex>-LC. Не умаляя общности, будем считать, что <tex>d \ge 2</tex>, так как для
<tex>d = 1</tex> задача становится тривиальной. Также будем считать, что <tex>\mathrm{MINCON}(M) > 0</tex>.
Элемент <tex>B</tex> единственный, кто покрывает область <tex>[V, 2V] \times \ldots \times [V, 2V]</tex>, объем которой превышает <tex>V</tex>. Единственным кандидатом на
должность минимального вкладчика, не присутствовавшего в начальном множестве <tex>M</tex>, является элемент <tex>C_{\lambda}</tex>. Его вклад в точности соответствуем соответствует области
<tex>[0, 1] \times \ldots \times [0, 1] \times [2V, 2V + \lambda]</tex>, объем которой равен <tex>\lambda</tex>.
Таким образом, элемент <tex>C_{\lambda}</tex> является минимальным вкладчиком только, если <tex>\lambda \le \mathrm{MINCON}(M)</tex>.
Так как умея решать задачу LC, мы можем проверять, является ли <tex>C_{\lambda}</tex> минимальным вкладчиком, можно
устроить двоичный поиск по велечине величине <tex>\lambda</tex>, чтобы найти <tex>\mathrm{MINCON}(M)</tex>, что
потребует <tex>O(\log(V))</tex> шагов. Однако в случае <tex>\varepsilon</tex>-LC запросов
обычный двоичный поиcк осуществить не удается. Несмотря на появившуюся неточность, продолжим выполнять
Вне этого интервала результат запроса всегда верен.
Используя такой двоичный поиск, мы получим число <tex>\kappa</tex>, которое или попадает в указанный интервал, и тогда задача решена, или является
максимальным целым числом , меньшим <tex>\log_2 \left((1 + \varepsilon)^{-1}\mathrm{MINCON}(M)\right)</tex>.
Таким образом, <tex>\lambda = 2^{\kappa} \ge \mathrm{MINCON}(M) / (2(1 + \varepsilon))</tex>, то есть была получена <tex>2(1 + \varepsilon)</tex> аппроксимация задачи MINCON.
