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

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

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

Учитывая набор элементов ( так называемый Вселенной ) и набор из множеств, объединение равняется вселенной, проблема набор крышка определить наименьший суб-коллекции , объединение которых равняется вселенной. Например, рассмотрим вселенную и набор множеств . Ясно, что объединение есть . Тем не менее, мы можем охватить все элементы со следующим, меньшим числом множеств: .${\ Displaystyle \ {1,2, ..., п \}}$${\ 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}} \ substeq {\ mathcal {S}}}$${\ displaystyle {\ mathcal {U}}}$${\ displaystyle ({\ mathcal {U}}, {\ mathcal {S}})}$${\ displaystyle k}$${\ displaystyle k}$${\ displaystyle ({\ mathcal {U}}, {\ mathcal {S}})}$

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

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

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

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

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

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

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

Формулировка набора ударов [ править ]

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

Жадный алгоритм [ править ]

Существует жадный алгоритм полиномиальной аппроксимации покрытия множества по времени, который выбирает множества по одному правилу: на каждом этапе выбирается набор, содержащий наибольшее количество непокрытых элементов. Этот метод может быть реализован во времени, линейном по сумме размеров входных наборов, с использованием очереди ведра для определения приоритетов наборов. ^[5] Достигается коэффициент приближения , где - размер охватываемого множества. ^[6] Другими словами, он находит покрытие, которое может быть в несколько раз больше минимального, где - номер -й гармоники :${\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}$$

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

Есть стандартный пример, на котором жадный алгоритм достигает коэффициента аппроксимации . Вселенная состоит из элементов. Система множеств состоит из попарно непересекающихся множеств с размерами соответственно, а также двух дополнительных непересекающихся множеств , каждое из которых содержит половину элементов из каждого . На этом входе жадный алгоритм берет наборы в указанном порядке, в то время как оптимальное решение состоит только из и . Пример такого ввода для изображен справа.${\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}$

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

Низкочастотные системы [ править ]

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

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

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

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

Когда речь идет о размере вселенной, Lund & Yannakakis (1994) показали, что покрытие множества не может быть аппроксимировано за полиномиальное время с точностью до множителя , если NP не имеет квазиполиномиальных временных алгоритмов. Файги (1998) улучшил эту нижнюю границу до при тех же предположениях, что по существу соответствует коэффициенту аппроксимации, достигнутому жадным алгоритмом. Раз и Сафра (1997) установили нижнюю границу , где - некоторая константа, при более слабом предположении, что P NP . Аналогичный результат с более высоким значением был недавно доказан Alon, Moshkovitz & Safra (2006).${\displaystyle n}$${\displaystyle {\tfrac {1}{2}}\log _{2}{n}\approx 0.72\ln {n}}$${\displaystyle {\bigl (}1-o(1){\bigr )}\cdot \ln {n}}$${\displaystyle c\cdot \ln {n}}$${\displaystyle c}$${\displaystyle \not =}$${\displaystyle c}$. Динур & Стурер (2013) показал оптимальную inapproximability путем доказательства того, что оно не может быть приближено к если P NP .${\displaystyle {\bigl (}1-o(1){\bigr )}\cdot \ln {n}}$${\displaystyle =}$

Обложка утяжеленного набора [ править ]

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

Связанные проблемы [ править ]

• Набор ударов эквивалентен переформулировке набора обложек.
• Вершинное покрытие - это частный случай ударного набора.
• Боковая крышка - это особый случай Set Cover.
• Покрытие геометрического набора - это особый случай Покрытия набора, когда вселенная представляет собой набор точек, а множества индуцируются пересечением вселенной и геометрических фигур (например, дисков, прямоугольников).${\displaystyle \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 and McGraw-Hill, стр. 1033–1038, ISBN 978-0-262-03293-3
• Feige, Уриэль (1998), "Порог Л п для аппроксимирующего множества крышки", Журнал ACM , 45 (4): 634-652, CiteSeerX  10.1.1.70.5014 , DOI : 10,1145 / 285055,285059 , ISSN  0004-5411 , S2CID  52827488.
• Карпинский, Марек; Зеликовский, Александр (1998), Аппроксимация плотных случаев покрывающих задач , 40 , стр. 169–178, ISBN 9780821870846
• Лунд, Карстен ; Yannakakis, Михалис (1994), "О твердости аппроксимирующих задач минимизации", Журнал ACM , 41 (5): 960-981, DOI : 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) , Грац, Австрия, DOI : 10,5281 / zenodo.10037

Внешние ссылки [ править ]

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

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