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

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

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

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

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

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

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

минимизировать	${\ displaystyle \ sum _ {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 для покрытия проблем . Целочисленность разрыв этого НРП самое большее , так что его релаксация дает фактор- алгоритм аппроксимации для минимальной задачи набор крышки (где есть размер Вселенной). ${\ 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}}$

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

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

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

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

{\ Displaystyle Н (п) = \ сумма _ {к = 1} ^ {n} {\ гидроразрыва {1} {k}} \ leq \ ln {n} +1}

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

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

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

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

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

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

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

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

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

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

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

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

Набор ударов эквивалентен переформулировке набора обложек.
Вершинное покрытие - это частный случай ударного набора.
Боковая крышка - это особый случай 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), "Аппроксимация плотных случаев покрывающих задач", Труды семинара DIMACS по проектированию сетей: возможность подключения и расположение объектов , 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) , Труды 25-го Международного семинара по принципам диагностики , Грац, Австрия, doi : 10.5281 / zenodo.10037

Languages

In other projects