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

Классическая задача комбинаторики

Пример задачи о покрытии множества.

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

Если задан набор элементов {1, 2, …, n } (далее именуемый универсумом , определяющим все возможные рассматриваемые элементы), и набор, обозначаемый S , из m заданных подмножеств, объединение которых равно универсуму, то задача покрытия множества состоит в определении наименьшего поднабора S , объединение которого равно универсуму.

Например, рассмотрим вселенную U = {1, 2, 3, 4, 5} и набор множеств S = { {1, 2, 3}, {2, 4}, {3, 4}, {4, 5} }. В этом примере m равно 4, так как существует четыре подмножества, которые составляют этот набор. Объединение S равно U . Однако мы можем покрыть все элементы только двумя множествами: { {1, 2, 3}, {4, 5} } ‍ , см. рисунок, но не только одним множеством. Следовательно, решение задачи покрытия множеств для этого U и S имеет размер 2.

Более формально, если задана вселенная и семейство подмножеств , то покрытие множеств — это подсемейство множеств, объединение которых равно . ${\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-полной . Это одна из 21 NP-полных задач Карпа, которая была показана как NP-полная в 1972 году. Версия оптимизации/поиска покрытия множеств является NP-трудной . ^[1] Это задача, «изучение которой привело к разработке фундаментальных методов для всей области» алгоритмов приближения . ^[2]

Варианты

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

В задаче о дробном покрытии множеств разрешено выбирать дроби множеств, а не целые множества. Дробное покрытие множеств — это присвоение дроби (числа в [0,1]) каждому множеству в , так что для каждого элемента 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 доля каждого набора. ${\displaystyle {\mathcal {S}}}$

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

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

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

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

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

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

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

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

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

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

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

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

Плотный пример для жадного алгоритма с 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}$

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

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

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

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

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

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

Когда речь идет о размере вселенной, Лунд и Яннакакис (1994) показали, что покрытие множеств не может быть приближено за полиномиальное время с точностью до множителя , если только NP не имеет алгоритмов с квазиполиномиальным временем . Фейги (1998) улучшили эту нижнюю границу до при тех же предположениях, что по сути соответствует коэффициенту приближения, достигнутому жадным алгоритмом. Раз и Сафра (1997) установили нижнюю границу , где — некоторая константа, при более слабом предположении, что P NP . Похожий результат с более высоким значением был недавно доказан Алоном, Мошковицем и Сафрой (2006). Динур и Штойрер (2013) показали оптимальную неаппроксимируемость, доказав, что ее нельзя приблизить до , если только P NP . ${\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}$ ${\displaystyle {\bigl (}1-o(1){\bigr )}\cdot \ln {n}}$ ${\displaystyle =}$

В низкочастотных системах Динур и др. (2003) доказали, что аппроксимировать покрытие множеств лучше, чем NP-трудно . Если гипотеза об уникальных играх верна, ее можно улучшить до, как доказали Хот и Регев (2008). ${\displaystyle f-1-\epsilon }$ ${\displaystyle f-\epsilon }$

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

Утяжеленный набор чехлов

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

Дробный набор крышек

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

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

Примечания

1. Корте и Виген 2012, стр. 414.
2. Вазирани (2001, стр. 15)
3. Вазирани (2001, стр. 108)
4. Вазирани (2001, стр. 110–112)
5. Нильсен, Франк (2000-09-06). "Быстрое закалывание ящиков в больших размерностях" (PDF) . Теоретическая информатика . 246 (1): 53–72. doi : 10.1016/S0304-3975(98)00336-3 . ISSN  0304-3975.
6. Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Стейн, Клиффорд (2009) [1990], «Упражнение 35.3-3», Введение в алгоритмы (3-е изд.), MIT Press и McGraw-Hill, стр. 1122, ISBN 0-262-03384-4
7. Chvatal, V. (август 1979), «Жадная эвристика для задачи покрытия множеств», Математика исследования операций , 4 (3): 233–235, doi :10.1287/moor.4.3.233, JSTOR  3689577
8. Карпински и Зеликовский 1998
9. Славик Петр Плотный анализ жадного алгоритма для покрытия множества. STOC'96, страницы 435-441, doi :10.1145/237814.237991
10. Вазирани (2001, стр. 118–119)
11. Вазирани (2001, Глава 14)
12. Информация., Sandia National Laboratories. США. Министерство энергетики. США. Министерство энергетики. Офис по научным и техническим вопросам (1999). О проблеме покрытия набора красным и синим. США. Министерство энергетики. OCLC  68396743.
13. Гейнер-Дьюар, Эндрю; Вера-Ликона, Паола (2017), «Проблема генерации минимального множества попаданий: алгоритмы и вычисления», SIAM Journal on Discrete Mathematics , 31 (1): 63–100, arXiv : 1601.02939 , doi : 10.1137/15M1055024, MR  3590650, S2CID  9240467

Ссылки

• Алон, Нога ; Мошковиц, Дана ; Сафра, Шмуэль (2006), «Алгоритмическое построение множеств для k-ограничений», ACM Trans. Algorithms , 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 для аппроксимации покрытия множеств», Журнал 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), «О сложности аппроксимации задач минимизации», Журнал 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{{citation}}: CS1 maint: location missing publisher (link)
• Динур, Ирит ; Гурусвами, Венкатесан ; Хот, Субхаш ; Регев, Одед (2003), Новый многослойный PCP и твердость покрытия вершин гиперграфа, Ассоциация вычислительной техники, стр. 595–601, doi : 10.1145/780542.780629, ISBN 1581136749
• Хот, Субхаш ; Регев, Одед (2008), Покрытие вершин может быть трудно аппроксимировать с точностью до 2− ϵ {\displaystyle \epsilon } , Журнал компьютерных и системных наук, стр. 335–349, doi :10.1016/j.jcss.2007.06.019
• Тревизан, Лука (2001), «Результаты неаппроксимируемости для задач оптимизации на экземплярах ограниченной степени», Труды тридцать третьего ежегодного симпозиума ACM по теории вычислений , Ассоциация вычислительной техники, стр. 453–461, doi :10.1145/380752.380839, ISBN 1-58113-349-9

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

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