Сложность задачи вычисления Least Hypervolume Contributor и задачи его аппроксимации
Гиперобъем является индикатором Парето фронта, набирающим в последнее время популярность. Важной составляющей многих оптимизирующих алгоритмов, использующих индикатор гиперобъема, является вычисление вклада одного элемента Парето фронта. К сожалению, даже вычисление минимального вклада (Minimal Contribution, MINCON) и нахождение соответствующего ему элемента (Least Contributor, LC) являются трудными задачами. Более того, даже аппроксимации этих задач являются NP-трудными.
Используемые обозначения
– гиперобъем множества .
– вклад элемента в гиперобъем.
– минимальный вклад в гиперобъем множества. Задача MINCON – задача нахождения .
– least contributor, минимальный вкладчик, элемент, имеющей минимальный вклад в гиперобъем. Задача LC – задача нахождения .
– элемент, имеющий вклад, отличающийся от минимального не более, чем в раз, то есть . Задача -LC – задача нахождения .
Все числа, за исключением
, будем считать целыми.Сложность задачи MINCON
Теорема: | ||
Задача MINCON является #P-трудной, а задача аппроксимации MINCON с точностью до является NP-трудной для любого . | ||
Доказательство: | ||
Для доказательства теоремы сведем задачу #MON-CNF к задаче MINCON. Про задачу #MON-CNF известно, что она является #P-трудной, а ее аппроксимация является NP-трудной.
Также добавим параллелепипед . Таким образом, множество будет состоять из элемента . Не умаляя общности, будем считать, что ни один клоз не доминируется другим, то есть для любых . Для каждого существуют такие , что область уникально покрывается только элементом , что означается, что для любого . Так как объем составляет лишь , то именно будет являться минимальным вкладчиком.Представим Из-за сведения получаем, что задача MINCON является #P-трудной, а ее аппроксимация является NP-трудной, даже когда минимальный вкладчик уже известен. в виде набора кубиков , где . Чтобы входил в , необходимо, чтобы не входил в . входит в , если для всех выполнено , то есть для всех , и . Получаем, что такой набор удовлетворяет для какого-то , то есть удовлетворяет . Таким образом, тогда и только тогда, когда удовлетворяет , то есть . | ||
Сложность задачи -LC
Теорема: |
Задача -LC является NP-трудной. |
Доказательство: |
Для доказательства этой теоремы сведем задачу MINCON к задаче -LC. Не умаляя общности, будем считать, что , так как для задача становится тривиальной. Также будем считать, что .Пусть – размер обрамляющего прямоугольного параллелепипеда множества . Очевидно, что .Определим новое множество элементов: , , , . Исходные элементы были сдвинуты вдоль первой оси, поэтому вклад этих элементов не изминился, так как добавленная часть покрывается новым элементом . Также отметим, что вклад каждого из элементов множества не превышает .Элемент единственный, кто покрывает область , объем которой превышает . Единственным кандидатом на должность минимального вкладчика, не присутствовавшего в начальном множестве , является элемент . Его вклад в точности соответствует области , объем которой равен . Таким образом, элемент является минимальным вкладчиком только, если .Так как умея решать задачу LC, мы можем проверять, является ли минимальным вкладчиком, можно устроить двоичный поиск по величине , чтобы найти , что потребует шагов. Однако в случае -LC запросов обычный двоичный поиcк осуществить не удается. Несмотря на появившуюся неточность, продолжим выполнять все шаги двоичного поиска как обычно.Использование Ранее было показано, что аппроксимация задачи MINCON является NP-трудной, таким образом, NP-трудность задачи -LC может привести двоичный поиск не туда. Будем искать только старший бит ответа, то есть положим , где – целое число. Так как мы имеем , то неправильный ответ на запрос может выдаваться только при . Вне этого интервала результат запроса всегда верен. Используя такой двоичный поиск, мы получим число , которое или попадает в указанный интервал, и тогда задача решена, или является максимальным целым числом, меньшим . Таким образом, , то есть была получена аппроксимация задачи MINCON. -LC доказана. |
Источники
- Bringmann K., Friedrich T. Approximating the least hypervolume contributor: NP-hard in general, but fast in practice (2009)