Задача покрытия множеств - классический вопрос комбинаторики , информатики , исследования операций и теории сложности . Это один из 21 NP-полных задач Карпа показанных быть NP-полным в 1972 году.
Это проблема, «изучение которой привело к развитию фундаментальных методов для всей области» аппроксимационных алгоритмов . [1]
Учитывая набор элементов ( так называемый Вселенной ) и набор из множеств, объединение равняется вселенной, проблема набор крышка определить наименьший суб-коллекции , объединение которых равняется вселенной. Например, рассмотрим вселенную и набор множеств . Ясно, что объединение есть . Тем не менее, мы можем охватить все элементы со следующим, меньшим числом множеств: .
Более формально, учитывая вселенную и семейство подмножеств , покрытие - это подсемейство множеств, объединение которых равно . В задаче решения, покрывающей множество , входом является пара и целое число ; вопрос в том, есть ли комплект покрытия такого размера или меньше. В задаче оптимизации покрытия множества входными данными является пара , и задача состоит в том, чтобы найти покрытие множества, которое использует наименьшее количество множеств.
Вариант решения покрытия набора является NP-полным , а вариант оптимизации / поиска покрытия набора является NP-сложным . [2]
Если каждому набору назначена стоимость, это становится проблемой покрытия взвешенного набора.
Формулировка целочисленной линейной программы [ править ]
Задачу минимального покрытия множества можно сформулировать в виде следующей целочисленной линейной программы (ЦЛП). [3]
свести к минимуму | (минимизировать количество комплектов) | ||
при условии | для всех | (покрыть каждый элемент вселенной) | |
для всех . | (каждый набор либо в обложке набора, либо нет) |
Этот ILP принадлежит к более общему классу ILP для покрытия проблем . Целочисленность разрыв этого НРП самое большее , так что его релаксация дает фактор- алгоритм аппроксимации для минимальной задачи набор крышки (где есть размер Вселенной). [4]
В оболочке взвешенных наборов наборам присваивается вес. Обозначим вес установленного через . Тогда число линейной программы , описывающей взвешенный набор крышки идентична приведенной выше, за исключением того, что целевая функция , чтобы минимизировать это .
Формулировка набора ударов [ править ]
Покрытие множества эквивалентно задаче попадания множества . Это можно увидеть, наблюдая, как пример покрытия множества может рассматриваться как произвольный двудольный граф , где множества представлены вершинами слева, вселенная представлена вершинами справа, а ребра представляют включение элементов в множества. Затем задача состоит в том, чтобы найти подмножество левых вершин с минимальной мощностью, которое покрывает все правые вершины. В задаче о множестве ударов цель состоит в том, чтобы покрыть левые вершины, используя минимальное подмножество правых вершин. Таким образом, переход от одной задачи к другой достигается перестановкой двух наборов вершин.
Жадный алгоритм [ править ]
Существует жадный алгоритм полиномиальной аппроксимации покрытия множества по времени, который выбирает множества по одному правилу: на каждом этапе выбирается набор, содержащий наибольшее количество непокрытых элементов. Этот метод может быть реализован во времени, линейном по сумме размеров входных наборов, с использованием очереди ведра для определения приоритетов наборов. [5] Достигается коэффициент приближения , где - размер охватываемого множества. [6] Другими словами, он находит покрытие, которое может быть в несколько раз больше минимального, где - номер -й гармоники :
Этот жадный алгоритм фактически достигает отношения аппроксимации, где - набор максимальной мощности . Однако для плотных экземпляров существует алгоритм -аппроксимации для каждого . [7]
Есть стандартный пример, на котором жадный алгоритм достигает коэффициента аппроксимации . Вселенная состоит из элементов. Система множеств состоит из попарно непересекающихся множеств с размерами соответственно, а также двух дополнительных непересекающихся множеств , каждое из которых содержит половину элементов из каждого . На этом входе жадный алгоритм берет наборы в указанном порядке, в то время как оптимальное решение состоит только из и . Пример такого ввода для изображен справа.
Результаты о неприближаемости показывают, что жадный алгоритм по существу является наилучшим из возможных алгоритмов аппроксимации за полиномиальное время для покрытия множества с точностью до членов более низкого порядка (см. Результаты о неприемлемости ниже) при правдоподобных предположениях о сложности. Более тщательный анализ жадного алгоритма показывает, что коэффициент аппроксимации точный . [8]
Низкочастотные системы [ править ]
Если каждый элемент встречается не более чем в наборах f , то решение может быть найдено за полиномиальное время, которое аппроксимирует оптимум с точностью до фактора f с использованием LP-релаксации .
Если ограничение заменяются для всех S в в целом числе линейной программы , показанной выше , то она становится (нецелой) линейной программой L . Алгоритм можно описать следующим образом:
- Найдите оптимальное решение O для программы L, используя некоторый полиномиальный метод решения линейных программ.
- Выберите все наборы S , для которого соответствующего переменных х S имеет значение по крайней мере 1 / п в растворе O . [9]
Результаты неприближаемости [ править ]
Когда речь идет о размере вселенной, Lund & Yannakakis (1994) показали, что покрытие множества не может быть аппроксимировано за полиномиальное время с точностью до множителя , если NP не имеет квазиполиномиальных временных алгоритмов. Файги (1998) улучшил эту нижнюю границу до при тех же предположениях, что по существу соответствует коэффициенту аппроксимации, достигнутому жадным алгоритмом. Раз и Сафра (1997) установили нижнюю границу , где - некоторая константа, при более слабом предположении, что P NP . Аналогичный результат с более высоким значением был недавно доказан Alon, Moshkovitz & Safra (2006).. Динур & Стурер (2013) показал оптимальную inapproximability путем доказательства того, что оно не может быть приближено к если P NP .
Обложка утяжеленного набора [ править ]
Этот раздел нуждается в расширении . Вы можете помочь, добавив к нему . ( Ноябрь 2017 г. ) |
Ослабляя целочисленную линейную программу для взвешенного покрытия множества, указанную выше , можно использовать рандомизированное округление, чтобы получить приближение -фактор. Соответствующий анализ невзвешенного покрытия набора описан в разделе « Рандомизированное округление # Алгоритм случайного округления для покрытия набора» и может быть адаптирован к взвешенному случаю. [10]
Связанные проблемы [ править ]
- Набор ударов эквивалентен переформулировке набора обложек.
- Вершинное покрытие - это частный случай ударного набора.
- Боковая крышка - это особый случай Set Cover.
- Покрытие геометрического набора - это особый случай обложки набора, когда вселенная представляет собой набор точек, а множества индуцируются пересечением вселенной и геометрических фигур (например, дисков, прямоугольников).
- Комплект упаковки
- Проблема максимального покрытия состоит в том, чтобы выбрать не более k наборов, чтобы охватить как можно больше элементов.
- Доминирующее множество - это проблема выбора набора вершин (доминирующего множества) в графе так, чтобы все остальные вершины были смежными хотя бы с одной вершиной в доминирующем множестве. Было показано, что проблема Доминирующего множества является NP-завершенной за счет сокращения из укрытия Сета.
- Проблема с точным покрытием состоит в том, чтобы выбрать комплект покрытия, в котором ни один элемент не входит более чем в один комплект покрытия.
Заметки [ править ]
- ^ Вазирани (2001 , стр. 15)
- ^ Корте & Vygen 2012 , стр. 414.
- ^ Вазирани (2001 , стр. 108)
- ^ Вазирани (2001 , стр. 110-112)
- ^ Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Стейн, Клиффорд (2009) [1990], «Упражнение 35.3-3», Введение в алгоритмы (3-е изд.), MIT Press and McGraw-Hill, p. 1122, ISBN 0-262-03384-4
- ^ Chvatal, В. Жадная эвристика для проблемы покрытия множеств . Математика исследования операций Vol. 4, No. 3 (август 1979 г.), стр. 233-235
- ^ Карпинский и Зеликовский 1998
- ^ Славик Петр Тщательный анализ жадного алгоритма покрытия множества . STOC'96, страницы 435-441, DOI : 10,1145 / 237814,237991
- ^ Вазирани (2001 , стр. 118-119)
- ^ Вазирани (2001 , глава 14)
Ссылки [ править ]
- Алон, Нога ; Мошковиц, Дана ; Сафра, Шмуэль (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