Сложность задачи вычисления Least Hypervolume Contributor и задачи его аппроксимации — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 13: Строка 13:
 
<tex>\mathrm{CON}(M, x) := \mathrm{HYP}(M) - \mathrm{HYP}(M \setminus x)</tex> – вклад элемента <tex>x \in M</tex> в гиперобъем.
 
<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> – минимальный вклад в гиперобъем множества.
+
<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, минимальный вкладчик, элемент, имеющей минимальный вклад в гиперобъем.
+
<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>\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>\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 ==
 
== Сложность задачи MINCON ==
Строка 55: Строка 55:
 
другим, то есть <tex>C_i \nsubseteq C_j</tex> для любых <tex>i \neq j</tex>.
 
другим, то есть <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>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>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> будет являться минимальным вкладчиком.
 
именно <tex>B</tex> будет являться минимальным вкладчиком.
  
Строка 78: Строка 78:
 
|proof=
 
|proof=
  
Для докозательства этой теоремы сведем задачу MINCON к задаче <tex>\varepsilon</tex>-LC. Не умаляя общности, будем считать, что <tex>d \ge 2</tex>, так как для
+
Для доказательства этой теоремы сведем задачу MINCON к задаче <tex>\varepsilon</tex>-LC. Не умаляя общности, будем считать, что <tex>d \ge 2</tex>, так как для
 
<tex>d = 1</tex> задача становится тривиальной. Также будем считать, что <tex>\mathrm{MINCON}(M) > 0</tex>.
 
<tex>d = 1</tex> задача становится тривиальной. Также будем считать, что <tex>\mathrm{MINCON}(M) > 0</tex>.
  
Строка 97: Строка 97:
  
 
Элемент <tex>B</tex> единственный, кто покрывает область <tex>[V, 2V] \times \ldots \times [V, 2V]</tex>, объем которой превышает <tex>V</tex>. Единственным кандидатом на
 
Элемент <tex>B</tex> единственный, кто покрывает область <tex>[V, 2V] \times \ldots \times [V, 2V]</tex>, объем которой превышает <tex>V</tex>. Единственным кандидатом на
должность минимального вкладчика, не присутствовавшего в начальном множестве <tex>M</tex>, является элемент <tex>C_{\lambda}</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>[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>.
 
Таким образом, элемент <tex>C_{\lambda}</tex> является минимальным вкладчиком только, если <tex>\lambda \le \mathrm{MINCON}(M)</tex>.
  
 
Так как умея решать задачу LC, мы можем проверять, является ли <tex>C_{\lambda}</tex> минимальным вкладчиком, можно
 
Так как умея решать задачу LC, мы можем проверять, является ли <tex>C_{\lambda}</tex> минимальным вкладчиком, можно
устроить двоичный поиск по велечине <tex>\lambda</tex>, чтобы найти <tex>\mathrm{MINCON}(M)</tex>, что
+
устроить двоичный поиск по величине <tex>\lambda</tex>, чтобы найти <tex>\mathrm{MINCON}(M)</tex>, что
 
потребует <tex>O(\log(V))</tex> шагов. Однако в случае <tex>\varepsilon</tex>-LC запросов
 
потребует <tex>O(\log(V))</tex> шагов. Однако в случае <tex>\varepsilon</tex>-LC запросов
 
обычный двоичный поиcк осуществить не удается. Несмотря на появившуюся неточность, продолжим выполнять
 
обычный двоичный поиcк осуществить не удается. Несмотря на появившуюся неточность, продолжим выполнять
Строка 113: Строка 113:
 
Вне этого интервала результат запроса всегда верен.
 
Вне этого интервала результат запроса всегда верен.
 
Используя такой двоичный поиск, мы получим число <tex>\kappa</tex>, которое или попадает в указанный интервал, и тогда задача решена, или является
 
Используя такой двоичный поиск, мы получим число <tex>\kappa</tex>, которое или попадает в указанный интервал, и тогда задача решена, или является
максимальным целым числом меньшим <tex>\log_2 \left((1 + \varepsilon)^{-1}\mathrm{MINCON}(M)\right)</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.
 
Таким образом, <tex>\lambda = 2^{\kappa} \ge \mathrm{MINCON}(M) / (2(1 + \varepsilon))</tex>, то есть была получена <tex>2(1 + \varepsilon)</tex> аппроксимация задачи MINCON.
  

Версия 13:38, 19 июня 2012

Эта статья находится в разработке!

Гиперобъем является индикатором Парето фронта, набирающим в последнее время популярность. Важной составляющей многих оптимизирующих алгоритмов, использующих индикатор гиперобъема, является вычисление вклада одного элемента Парето фронта. К сожалению, даже вычисление минимального вклада (Minimal Contribution, MINCON) и нахождение соответсвующего ему элемента (Least Contributor, LC) являются трудными задачами. Более того, даже аппроксимации этих задач являются NP-трудными.

Используемые обозначения

[math]\mathrm{HYP}\left(M\right)[/math] – гиперобъем множества [math]M[/math].

[math]\mathrm{CON}(M, x) := \mathrm{HYP}(M) - \mathrm{HYP}(M \setminus x)[/math] – вклад элемента [math]x \in M[/math] в гиперобъем.

[math]\mathrm{MINCON}(M) := \min \limits_{x \in M} \mathrm{CON}(M, x)[/math] – минимальный вклад в гиперобъем множества. Задача MINCON – задача нахождения [math]\mathrm{MINCON}(M)[/math].

[math]\mathrm{LC}(M) := \mathrm{argmin}_{x \in M} \mathrm{CON}(M, x)[/math] – least contributor, минимальный вкладчик, элемент, имеющей минимальный вклад в гиперобъем. Задача LC – задача нахождения [math]\mathrm{LC}(M)[/math].

[math]\varepsilon\text{-}\mathrm{LC}(M)[/math] – элемент, имеющий вклад, отличающийся от минимального не более, чем в [math]1 + \varepsilon[/math] раз, то есть [math]\mathrm{CON}(M, \varepsilon\text{-}\mathrm{LC}(M)) \le (1 + \varepsilon)\mathrm{MINCON}(M)[/math]. Задача [math]\varepsilon[/math]-LC – задача нахождения [math]\varepsilon\text{-}\mathrm{LC}(M)[/math].

Сложность задачи MINCON

Теорема:
Задача MINCON является #P-трудной, а задача аппроксимации MINCON с точностью до [math]2^{d^{1 - \varepsilon}}[/math] является NP-трудной для любого [math]\varepsilon \gt 0[/math].
Доказательство:
[math]\triangleright[/math]

Для доказательства теоремы сведем задачу #MON-CNF к задаче MINCON. Про задачу #MON-CNF известно, что она является #P-трудной, а ее аппроксимация является NP-трудной.


Определение:
Задача #MON-CNF – задача нахождения числа удовлетворяющих подстановок для монотонной булевой формулы, записанной в КНФ, [math]f = \bigwedge \limits_{k=1}^n \bigvee \limits_{i \in C_k} x_i[/math], где клозы [math] C_k \subseteq {\{1,...,d\}}[/math].


За [math]\Box(a_1, \ldots, a_d)[/math] будем обозначать прямоугольный гиперпараллелепипед [math][0, a_1] \times \ldots \times [0, a_d][/math]. Пусть [math]f = \bigwedge \limits_{k=1}^n \bigvee \limits_{i \in C_k} x_i[/math] – монотонная булева формула в КНФ, [math] C_k \subseteq {\{1,...,d\}}[/math]. Построим параллелепипеды [math]A_k = \Box(a_1^k, \ldots, a_d^k, 2^d + 2) \subseteq \mathbb{R}^{d+1}[/math] для каждого клоза формулы, при этом

[math]a_i^k = \begin{cases} 1,~\text{if}~i \in C_k \\ 2,~\text{otherwise} \end{cases} [/math]

Также добавим параллелепипед [math]B = \Box(2, \ldots, 2, 1) \subseteq \mathbb{R}^{d+1}[/math]. Таким образом, множество [math]M[/math] будет состоять из [math]n + 1[/math] элемента [math]\{A_1, \ldots, A_n, B\}[/math]. Не умаляя общности, будем считать, что ни один клоз не доминируется другим, то есть [math]C_i \nsubseteq C_j[/math] для любых [math]i \neq j[/math]. Для каждого [math]A_k[/math] существуют такие [math]x_i = a_i^k - 1[/math], что область [math][x_1, x_1 + 1] \times \ldots \times [x_d, x_d + 1] \times [1, 2^d + 2][/math] уникально покрывается только элементом [math]A_k[/math], что означается, что [math]\mathrm{CON}(M, A_k) \gt 2^d[/math] для любого [math]k[/math]. Так как объем [math]B[/math] составляет лишь [math]2^d[/math], то именно [math]B[/math] будет являться минимальным вкладчиком.

Представим [math]B[/math] в виде набора кубиков [math]B_x = [x_1, x_1 + 1] \times \ldots \times [x_d, x_d + 1] \times [0, 1][/math], где [math]x_i \in \{0, 1\}[/math]. Чтобы [math]B_x[/math] входил в [math]\mathrm{CON}(M, B)[/math], необходимо, чтобы [math]B_x[/math] не входил в [math]\bigcup \limits_{k = 1}^n A_k[/math]. [math]B_x[/math] входит в [math]A_k[/math], если для всех [math]i \in \{1, \ldots, d\}[/math] выполнено [math]x_i + 1 \le a_i^k[/math], то есть [math]a_i^k = 2[/math] для всех [math]x_i = 1[/math], и [math]i \notin C_k[/math]. Получаем, что такой набор [math](x_1, \ldots, x_d)[/math] удовлетворяет [math]\bigwedge \limits_{i \in C_k} \lnot x_i[/math] для какого-то [math]k[/math], то есть [math](x_1, \ldots, x_d)[/math] удовлетворяет [math]\overline{f} = \bigvee \limits_{k=1}^n \bigwedge \limits_{i \in C_k} \lnot x_i[/math]. Таким образом, [math]B_x \subseteq \mathrm{CON}(M, B)[/math] тогда и только тогда, когда [math](x_1, \ldots, x_d)[/math] удовлетворяет [math]f[/math], то есть [math]\mathrm{MINCON}(M) = \mathrm{CON}(M, B) = \left\vert\left\{ \left(x_1, \ldots, x_d \right) \in \left\{0, 1\right\}^d | \left(x_1, \ldots, x_d \right) \text{ satisfies } f \right\}\right\vert[/math].

Из-за сведения получаем, что задача MINCON является #P-трудной, а ее аппроксимация является NP-трудной, даже когда минимальный вкладчик уже известен.
[math]\triangleleft[/math]

Сложность задачи [math]\varepsilon[/math]-LC

Теорема:
Задача [math]\varepsilon[/math]-LC является NP-трудной.
Доказательство:
[math]\triangleright[/math]

Для доказательства этой теоремы сведем задачу MINCON к задаче [math]\varepsilon[/math]-LC. Не умаляя общности, будем считать, что [math]d \ge 2[/math], так как для [math]d = 1[/math] задача становится тривиальной. Также будем считать, что [math]\mathrm{MINCON}(M) \gt 0[/math].

Пусть [math]V[/math] – размер обрамляющего прямоугольного параллелепипеда множества [math]M[/math]. Очевидно, что [math]V \le 2^{\text{input size}}[/math].

Определим новое множество элементов:

[math]A = \left\{\Box\left(a_1 + 2V, a_2, \ldots, a_d\right) | \left(a_1, \ldots, a_d\right) \in M\right\}[/math],

[math]B = \Box \left(2V, \ldots, 2V\right)[/math],

[math]C_{\lambda} = \Box \left(1, \ldots, 1, 2V + \lambda \right)[/math],

[math]M_{\lambda} = A \cup \{B\} \cup \{ C_{\lambda} \}[/math].

Исходные элементы были сдвинуты вдоль первой оси, поэтому вклад этих элементов не изминился, так как добавленная часть покрывается новым элементом [math]B[/math]. Также отметим, что вклад каждого из элементов множества [math]A[/math] не превышает [math]V[/math].

Элемент [math]B[/math] единственный, кто покрывает область [math][V, 2V] \times \ldots \times [V, 2V][/math], объем которой превышает [math]V[/math]. Единственным кандидатом на должность минимального вкладчика, не присутствовавшего в начальном множестве [math]M[/math], является элемент [math]C_{\lambda}[/math]. Его вклад в точности соответствует области [math][0, 1] \times \ldots \times [0, 1] \times [2V, 2V + \lambda][/math], объем которой равен [math]\lambda[/math]. Таким образом, элемент [math]C_{\lambda}[/math] является минимальным вкладчиком только, если [math]\lambda \le \mathrm{MINCON}(M)[/math].

Так как умея решать задачу LC, мы можем проверять, является ли [math]C_{\lambda}[/math] минимальным вкладчиком, можно устроить двоичный поиск по величине [math]\lambda[/math], чтобы найти [math]\mathrm{MINCON}(M)[/math], что потребует [math]O(\log(V))[/math] шагов. Однако в случае [math]\varepsilon[/math]-LC запросов обычный двоичный поиcк осуществить не удается. Несмотря на появившуюся неточность, продолжим выполнять все шаги двоичного поиска как обычно.

Использование [math]\varepsilon[/math]-LC может привести двоичный поиск не туда. Будем искать только старший бит ответа, то есть положим [math]\lambda = 2^{\kappa}[/math], где [math]\kappa[/math] – целое число. Так как мы имеем [math]\mathrm{CON}(M, \varepsilon\text{-LC}(M)) \le (1 + \varepsilon) \mathrm{MINCON}(M)[/math], то неправильный ответ на запрос может выдаваться только при [math](1 + \varepsilon)^{-1}\mathrm{MINCON}(M) \le 2^{\kappa} \le (1 + \varepsilon)\mathrm{MINCON}(M)[/math]. Вне этого интервала результат запроса всегда верен. Используя такой двоичный поиск, мы получим число [math]\kappa[/math], которое или попадает в указанный интервал, и тогда задача решена, или является максимальным целым числом, меньшим [math]\log_2 \left((1 + \varepsilon)^{-1}\mathrm{MINCON}(M)\right)[/math]. Таким образом, [math]\lambda = 2^{\kappa} \ge \mathrm{MINCON}(M) / (2(1 + \varepsilon))[/math], то есть была получена [math]2(1 + \varepsilon)[/math] аппроксимация задачи MINCON.

Ранее было показано, что аппроксимация задачи MINCON является NP-трудной, таким образом, NP-трудность задачи [math]\varepsilon[/math]-LC доказана.
[math]\triangleleft[/math]

Источники

  1. Bringmann K., Friedrich T. Approximating the least hypervolume contributor: NP-hard in general, but fast in practice (2009)