Установить проблему с крышкой - Set cover problem

В установить проблему прикрытия это классический вопрос в комбинаторика, Информатика, исследование операций, и теория сложности. Это один из 21 NP-полная задача Карпа показано как НП-полный в 1972 г.

Это проблема, «изучение которой привело к разработке фундаментальных методов для всей области» аппроксимационные алгоритмы.^[1]

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

Более формально, учитывая вселенную ${\displaystyle {\mathcal {U}}}$ и семья ${\displaystyle {\mathcal {S}}}$ подмножеств ${\displaystyle {\mathcal {U}}}$, а крышка это подсемейство ${\displaystyle {\mathcal {C}}\subseteq {\mathcal {S}}}$ множеств, объединение которых ${\displaystyle {\mathcal {U}}}$. В комплекте покрытие проблема решения, вход - пара ${\displaystyle ({\mathcal {U}},{\mathcal {S}})}$ и целое число ${\displaystyle k}$; вопрос в том, есть ли в комплекте покрытие размера ${\displaystyle k}$ или менее. В комплекте покрытие проблема оптимизации, вход - пара ${\displaystyle ({\mathcal {U}},{\mathcal {S}})}$, и задача состоит в том, чтобы найти покрытие множества, использующее наименьшее количество множеств.

Вариант решения покрытия множества: НП-полный, а оптимизация / поисковая версия обложки набора NP-жесткий.^[2]

Если каждому набору назначена стоимость, он становится взвешенный установить проблему с крышкой.

Формулировка целочисленной линейной программы

Задачу минимального покрытия можно сформулировать следующим образом целочисленная линейная программа (ILP).^[3]

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

Этот ILP принадлежит к более общему классу ILP для покрытие проблем. разрыв целостности этой ПДОДИ не более ${\displaystyle \scriptstyle \log n}$, так что это расслабление дает фактор-${\displaystyle \scriptstyle \log n}$ алгоритм аппроксимации для задачи минимального покрытия (где ${\displaystyle \scriptstyle n}$ это размер Вселенной).^[4]

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

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

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

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

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

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

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

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

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

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

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

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

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

1. Найдите оптимальное решение О для программы L с использованием некоторого полиномиального метода решения линейных программ.
2. Выбрать все наборы S для которого соответствующая переменная Икс_S имеет значение не менее 1 /ж в растворе О.^[8]

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

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

Крышка утяжеленного набора

Расслабляющий указана целочисленная линейная программа для взвешенного покрытия множества над, можно использовать рандомизированное округление получить ${\displaystyle O(\log n)}$-факторное приближение. Соответствующий анализ для невзвешенного покрытия множеств представлен в Рандомизированное округление # Алгоритм рандомизированного округления для заданного покрытия и может быть адаптирован к взвешенному случаю.^[9]

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

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

Примечания

1. Вазирани (2001), п. 15)
2. Корте и Выген 2012, п. 414.
3. Вазирани (2001), п. 108)
4. Вазирани (2001), стр. 110–112).
5. Чватал, В. Жадная эвристика для задачи о покрытии множеств. Математика исследования операций Vol. 4, No. 3 (август 1979 г.), стр. 233-235
6. Карпинский и Зеликовский 1998
7. Славик Петр Тщательный анализ жадного алгоритма установки покрытия. STOC'96, страницы 435-441, Дои:10.1145/237814.237991
8. Вазирани (2001), стр. 118–119).
9. Вазирани (2001), Глава 14)

Рекомендации

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

внешняя ссылка

• Контрольные показатели со скрытыми оптимальными решениями для покрытия наборов, упаковки наборов и определения победителя
• Сборник задач оптимизации NP - Minimum Set Cover