Установить проблему с обложкой

Пример примера проблемы с покрытием набора.

Проблема покрытия множеств — классический вопрос комбинаторики , информатики , исследования операций и теории сложности .

Учитывая набор элементов {1, 2, …, n } (называемый вселенной ) и коллекцию S из m подмножеств, объединение которых равно вселенной, задача покрытия множества состоит в том, чтобы идентифицировать наименьшую подколлекцию S , объединение которой равно вселенная. Например, рассмотрим вселенную U = {1, 2, 3, 4, 5} и набор множеств S = { {1, 2, 3}, {2, 4}, {3, 4}, {4, 5} }. Очевидно, что объединение S есть U . Однако мы можем охватить все элементы только двумя наборами: { {1, 2, 3}, {4, 5} }, см. рисунок. Следовательно, решение задачи о покрытии множеств имеет размер 2.

Более формально, учитывая вселенную ${\mathcal {U}}$ и семья ${\mathcal {S}}$ подмножеств ${\mathcal {U}}$, обложка множества — это подсемейство ${\mathcal {C}}\subseteq {\mathcal {S}}$ множеств, объединение которых есть ${\mathcal {U}}$.

• множества покрытий В задаче решения входными данными является пара $({\mathcal {U}},{\mathcal {S}})$ и целое число $k$; вопрос есть ли в комплекте чехол размера $k$ или меньше.
• покрытия набора В задаче оптимизации входными данными является пара $({\mathcal {U}},{\mathcal {S}})$, и задача состоит в том, чтобы найти обложку набора, в которой используется наименьшее количество наборов.

Вариант решения покрытия множества NP-полный . Это одна из 21 NP-полной задачи Карпа, которая, как было показано в 1972 году, является NP-полной . Версия покрытия множества для оптимизации/поиска является NP-трудной . Это проблема, «чье исследование привело к разработке фундаментальных методов для всей области» аппроксимационных алгоритмов .

Варианты

В задаче о покрытии взвешенного множества каждому набору присваивается положительный вес (представляющий его стоимость), и цель состоит в том, чтобы найти покрытие множества с наименьшим весом. Обычная (невзвешенная) обложка набора соответствует всем наборам, имеющим вес 1.

В задаче о покрытии дробных множеств допускается выбирать дробные части множеств, а не целые множества. Покрытие дробного множества — это присвоение дроби (числа в [0,1]) каждому множеству в ${\mathcal {S}}$, такой, что для каждого элемента x во вселенной сумма дробей множеств, содержащих x, равна как минимум 1. Цель состоит в том, чтобы найти покрытие дробного множества, в котором сумма дробей будет как можно меньше. Обратите внимание, что (обычное) покрытие множества эквивалентно покрытию дробного множества, в котором все дроби равны 0 или 1; следовательно, размер наименьшего дробного покрытия не превышает размера наименьшего покрытия, но может быть меньше. Например, рассмотрим вселенную U = {1, 2, 3} и набор множеств S = { {1, 2}, {2, 3}, {3, 1} }. Наименьшее покрытие набора имеет размер 2, например { {1, 2}, {2, 3} }. Но существует дробное покрытие набора размером 1,5, в котором от каждого набора берется 0,5 дроби.

линейной

Задачу покрытия множества можно сформулировать в виде следующей целочисленной линейной программы (ЦЛП).

минимизировать	$\sum _{s\in {\mathcal {S}}}x_{s}$		(минимизировать количество подходов)
при условии	$\sum _{s\colon e\in s}x_{s}\geqslant 1$	для всех $e\in {\mathcal {U}}$	(охватить каждый элемент вселенной)
	$x_{s}\in \{0,1\}$	для всех $s\in {\mathcal {S}}$.	(каждый набор либо в обложке набора, либо нет)

Для более компактного представления ограничения покрытия можно определить матрицу инцидентности $A$, где каждая строка соответствует элементу, а каждый столбец соответствует набору, и $A_{e,s}=1$ если элемент e находится в наборе s, и $A_{e,s}=0$ в противном случае. Тогда ограничение покрытия можно записать как $Ax\geqslant 1$.

Покрытие взвешенного множества описывается программой, идентичной приведенной выше, за исключением того, что целевая функция, которую необходимо минимизировать, равна $\sum _{s\in {\mathcal {S}}}w_{s}x_{s}$, где $w_{s}$ это вес комплекта $s\in {\mathcal {S}}$.

Покрытие дробного множества описывается программой, идентичной приведенной выше, за исключением того, что $x_{s}$ может быть нецелым, поэтому последнее ограничение заменяется на $0\leq x_{s}\leq 1$.

Эта линейная программа принадлежит к более общему классу ЛП для покрытия задач , поскольку все коэффициенты целевой функции и обе стороны ограничений неотрицательны. Разрыв целостности ПДОДИ составляет не более $\scriptstyle \log n$ (где $\scriptstyle n$ это размер Вселенной). Показано, что его релаксация действительно дает фактор- $\scriptstyle \log n$ аппроксимационный алгоритм решения задачи о покрытии минимального множества. см. в разделе рандомизированное округление#setcover Подробное объяснение .

Формулировка набора ударов

Покрытие множества эквивалентно проблеме попадания в множество . В этом можно убедиться, заметив, что случай покрытия множества можетможно рассматривать как произвольный двудольный граф , в котором вселенная представлена ​​вершинами слева, а множества — вершинами слева.справа и ребра, обозначающие принадлежность элементов множествам. Тогда задача состоит в том, чтобы найти подмножество левых вершин минимальной мощности, которое имеет нетривиальное пересечение с каждой из правых вершин, что и является проблемой множества попаданий.

В области вычислительной геометрии набор ударов для набора геометрических объектов также называется набором ударов или набором прокалывания .

Жадный алгоритм

Существует жадный алгоритм полиномиальной аппроксимации покрытия множеств, который выбирает множества по одному правилу: на каждом этапе выбирается то множество, которое содержит наибольшее количество непокрытых элементов. Этот метод может быть реализован во времени, линейном по сумме размеров входных наборов, с использованием очереди сегментов для определения приоритетов наборов. Он достигает коэффициента аппроксимации $H(s)$, где $s$ - это размер набора, который необходимо покрыть. Другими словами, он находит покрытие, которое может быть $H(n)$ раз больше минимального, где $H(n)$ это $n$ -й номер гармоники :

$$H(n)=\sum _{k=1}^{n}{\frac {1}{k}}\leq \ln {n}+1$$

Этот жадный алгоритм фактически достигает коэффициента аппроксимации $H(s^{\prime })$ где $s^{\prime }$ - это набор максимальной мощности $S$. Для $\delta -$плотные примеры, однако существует $c\ln {m}$-алгоритм аппроксимации для каждого $c>0$.

Плотный пример жадного алгоритма с k=3

Существует стандартный пример, в котором жадный алгоритм достигает коэффициента аппроксимации $\log _{2}(n)/2$.Вселенная состоит из $n=2^{(k+1)}-2$ элементы. Система комплектов состоит из $k$ попарно непересекающиеся множества $S_{1},\ldots ,S_{k}$ с размерами $2,4,8,\ldots ,2^{k}$ соответственно, а также два дополнительных непересекающихся множества $T_{0},T_{1}$,каждый из которых содержит половину элементов из каждого $S_{i}$. На этих входных данных жадный алгоритм принимает наборы $S_{k},\ldots ,S_{1}$, именно в таком порядке, а оптимальное решение состоит только из $T_{0}$ и $T_{1}$.Пример такого ввода для $k=3$ изображено справа.

Результаты о неаппроксимируемости показывают, что жадный алгоритм по существу является наилучшим из возможных алгоритмов аппроксимации с полиномиальным временем для покрытия множеств до членов более низкого порядка.(см. результаты о неаппроксимируемости ниже) при правдоподобных предположениях о сложности. Более тщательный анализ жадного алгоритма показывает, что коэффициент аппроксимации точно равен $\ln {n}-\ln {\ln {n}}+\Theta (1)$.

Низкочастотные системы

Если каждый элемент встречается не более чем в f наборах, то решение может быть найдено за полиномиальное время, которое аппроксимирует оптимум с точностью до коэффициента f, используя LP-релаксацию .

Если ограничение $x_{S}\in \{0,1\}$ заменяется на $x_{S}\geq 0$ для всех S в ${\mathcal {S}}$ в целочисленной линейной программе, показанной выше , она становится (нецелочисленной) линейной L. программой Алгоритм можно описать следующим образом:

1. Найдите оптимальное решение O для программы L, используя некоторый полиномиальный метод решения линейных программ.
2. Выберите все наборы S , для которых соответствующая переменная x _S имеет значение не менее 1/ f в решении O .

Результаты неаппроксимируемости

Когда $n$ относится к размеру Вселенной, Лунд и Яннакакис (1994) показали, что покрытие множеств не может быть аппроксимировано за полиномиальное время с точностью до коэффициента ${\tfrac {1}{2}}\log _{2}{n}\approx 0.72\ln {n}$, если только NP не имеет алгоритмов с квазиполиномиальным временем . Файги (1998) улучшил эту нижнюю границу до ${\bigl (}1-o(1){\bigr )}\cdot \ln {n}$ при тех же предположениях, что по существу соответствует коэффициенту аппроксимации, полученному жадным алгоритмом. Раз и Сафра (1997) установили нижнюю границу.из $c\cdot \ln {n}$, где $c$ — некоторая константа в более слабом предположении, что P $\not =$НП .Аналогичный результат с более высоким значением $c$ недавно было доказано Алоном, Мошковицем и Сафрой (2006) . Динур и Стойрер (2013) показали оптимальную неаппроксимируемость, доказав, что ее нельзя аппроксимировать к ${\bigl (}1-o(1){\bigr )}\cdot \ln {n}$ если только П $=$Э.Г. ​

В низкочастотных системах Динур и др. (2003) доказали, что NP-трудно аппроксимировать покрытие множества лучше, чем $f-1-\epsilon$.Если гипотеза об уникальных играх верна, ее можно улучшить до $f-\epsilon$ as proven by Khot & Regev (2008) .

Тревизан (2001) доказывает, что наборы покрывают экземпляры с наборами размера не более $\Delta$ не может быть аппроксимировано с коэффициентом лучше, чем $\ln \Delta -O(\ln \ln \Delta )$ если только П $=$NP , тем самым делая аппроксимацию $\ln \Delta +1$ Жадный алгоритм в этом случае существенно точен.

Обложка взвешенного набора

Ослабляя целочисленную линейную программу для покрытия взвешенного множества описанную выше , можно использовать рандомизированное округление, чтобы получить $O(\log n)$-факторная аппроксимация. Неутяжеленную крышку комплекта можно адаптировать к утяжеленному кейсу.

Связанные проблемы

• Удар по сету — это эквивалентная переформулировка Set Cover.
• Покрытие вершин — это частный случай Hitting Set.
• Edge Cover — это особый случай Set Cover.
• Покрытие геометрического множества — это особый случай покрытия множества, когда вселенная представляет собой набор точек в $\mathbb {R} ^{d}$ а множества индуцируются пересечением Вселенной и геометрических фигур (например, дисков, прямоугольников).
• Упаковка комплекта
• Задача максимального покрытия состоит в том, чтобы выбрать не более k наборов, чтобы охватить как можно больше элементов.
• Доминирующее множество — это задача выбора набора вершин (доминирующего множества) в графе такого, чтобы все остальные вершины были смежны хотя бы с одной вершиной в доминирующем множестве. Было показано, что задача о доминирующем множестве является NP-полной за счет редукции от покрытия множества.
• Точная задача покрытия состоит в том, чтобы выбрать покрытие множества, в котором ни один элемент не входит более чем в одно покрывающее множество.
• Обложка красно-синего комплекта.
• Похищение прикрытия .
• Монотонная дуализация — это вычислительная задача, эквивалентная перечислению всех минимальных наборов попаданий или перечислению всех покрытий минимальных множеств данного семейства множеств.

Ссылки

• Алон, Нога ; Мошковитц, Дана ; Сафра, Шмуэль (2006), «Алгоритмическое построение множеств для k-ограничений», ACM Trans. Алгоритмы , 2 (2): 153–177, CiteSeerX   10.1.1.138.8682 , doi : 10.1145/1150334.1150336 , ISSN   1549-6325 , S2CID   11922650 .
• Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Стейн, Клиффорд (2001), Введение в алгоритмы , Кембридж, Массачусетс: MIT Press и McGraw-Hill, стр. 1033–1038, ISBN.  978-0-262-03293-3
• Файги, Уриэль (1998), «Порог ln n для аппроксимации покрытия набора», Journal of the ACM , 45 (4): 634–652, CiteSeerX   10.1.1.70.5014 , doi : 10.1145/285055.285059 , ISSN   0004-5411 , S2CID   52827488 .
• Карпински, Марек; Зеликовский, Александр (1998), «Аппроксимация плотных случаев покрытия проблем», Труды семинара DIMACS по проектированию сетей: возможности подключения и расположение объектов , том. 40, Американское математическое общество, стр. 169–178, ISBN.  9780821870846
• Лунд, Карстен ; Яннакакис, Михалис (1994), «О сложности аппроксимации задач минимизации», Journal of the ACM , 41 (5): 960–981, doi : 10.1145/185675.306789 , ISSN   0004-5411 , S2CID   9021065 .
• Раз, Ран ; Сафра, Шмуэль (1997), «Тест низкой степени с субпостоянной вероятностью ошибки и характеристика NP с субпостоянной вероятностью ошибки PCP», STOC '97: Материалы двадцать девятого ежегодного симпозиума ACM по теории вычисления , ACM, стр. 475–484, ISBN.  978-0-89791-888-6 .
• Динур, Ирит ; Стойрер, Дэвид (2013), «Аналитический подход к параллельному повторению», STOC '14: Материалы сорок шестого ежегодного симпозиума ACM по теории вычислений , ACM, стр. 624–633 .
• Vazirani, Vijay V. (2001), Approximation Algorithms (PDF) , Springer-Verlag, ISBN  978-3-540-65367-7
• Корте, Бернхард ; Виген, Йенс (2012), Комбинаторная оптимизация: теория и алгоритмы (5-е изд.), Springer, ISBN  978-3-642-24487-2
• Кардосо, Нуно; Абреу, Руи (2014), «Эффективный распределенный алгоритм для вычисления минимальных наборов совпадений» (PDF) , Материалы 25-го международного семинара по принципам диагностики , Грац, Австрия, doi : 10.5281/zenodo.10037 {{citation}}: CS1 maint: отсутствует местоположение издателя ( ссылка )
• Динур, Ирит ; Гурусвами, Венкатесан ; Хот, Субхаш ; Регев, Одед (2003), Новый многослойный PCP и твердость покрытия вершин гиперграфа , Ассоциация вычислительной техники, стр. 595–601, ISBN  1581136749
• Хот, Субхаш ; Регев, Одед (2008), Вершинное покрытие может быть трудно аппроксимировать с точностью до 2−. $\epsilon$, Журнал компьютерных и системных наук, стр. 335–349.
• Тревизан, Лука (2001), Результаты о неаппроксимируемости задач оптимизации в экземплярах с ограниченной степенью , Ассоциация вычислительной техники, стр. 453–461.

Внешние ссылки

• Тесты со скрытыми оптимальными решениями для покрытия сетов, упаковки сетов и определения победителей
• Сборник задач оптимизации NP - Покрытие минимального набора