Проблемы покрытия

Тип вычислительной задачи

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

Наиболее яркими примерами задач покрытия являются задача покрытия множеств , которая эквивалентна задаче покрытия множеств , и ее частные случаи — задача покрытия вершин и задача покрытия ребер .

Задачи покрытия допускают перекрытие покрывающих примитивов; процесс покрытия чего-либо неперекрывающимися примитивами называется декомпозицией .

Общая формулировка линейного программирования

В контексте линейного программирования можно рассматривать любую минимизирующую линейную программу как задачу покрытия, если коэффициенты в матрице ограничений , целевой функции и правой части неотрицательны. ^[1] Точнее, рассмотрим следующую общую целочисленную линейную программу :

Такая задача целочисленного линейного программирования называется задачей покрытия, если для всех и . ${\displaystyle a_{ji},b_{j},c_{i}\geq 0}$ ${\displaystyle i=1,\dots ,n}$ ${\displaystyle j=1,\dots ,m}$

Интуиция: Предположим, что есть типы object и каждый объект типа имеет связанную стоимость . Число указывает, сколько объектов типа мы покупаем. Если ограничения выполнены, говорят, что это покрытие (структуры, которые покрываются, зависят от комбинаторного контекста). Наконец, оптимальное решение для приведенной выше целочисленной линейной программы — это покрытие минимальной стоимости. ${\displaystyle n}$ ${\displaystyle i}$ ${\displaystyle c_{i}}$ ${\displaystyle x_{i}}$ ${\displaystyle i}$ ${\displaystyle A\mathbf {x} \geq \mathbf {b} }$ ${\displaystyle \mathbf {x} }$

Виды покрытия проблем

Существуют различные виды задач покрытия в теории графов , вычислительной геометрии и других областях; см. Категория:Проблемы покрытия . Можно найти и другие стохастические версии этой задачи. ^[2]

Покрытие в сетях Петри

Для сетей Петри проблема покрытия определяется как вопрос о том, существует ли для данной маркировки прогон сети, такой, что может быть достигнута некоторая большая (или равная) маркировка. Больше здесь означает, что все компоненты по крайней мере такие же большие, как компоненты данной маркировки, и по крайней мере один из них по существу больше.

Радужное покрытие

В некоторых задачах покрытия покрытие должно удовлетворять некоторым дополнительным требованиям. В частности, в задаче радужного покрытия каждый из исходных объектов имеет «цвет», и требуется, чтобы покрытие содержало ровно один (или не более одного) объекта каждого цвета. Радужное покрытие изучалось, например, для покрытия точек интервалами : [ ^3]

• На действительной прямой имеется множество J из n цветных интервалов и множество P точек на действительной прямой.
• Подмножество Q множества J называется радужным множеством , если оно содержит не более одного интервала каждого цвета.
• Множество интервалов J называется покрытием P , если каждая точка из P содержится хотя бы в одном интервале Q.
• Задача о радужном покрытии — это задача нахождения радужного множества Q , которое является покрытием P.

Задача NP-трудная (путем сведения к линейной SAT ).

Бесконфликтное покрытие

Более общее понятие – бесконфликтное покрытие . ^[4] В этой задаче:

• Имеется множество O из m объектов и граф конфликтов G _O на O.
• Подмножество Q множества O называется бесконфликтным, если оно является независимым множеством в G _O , то есть никакие два объекта из Q не соединены ребром в G _O .
• Радужный набор — это бесконфликтный набор в частном случае, когда G _O состоит из непересекающихся клик, где каждая клика представляет цвет.

Бесконфликтное покрытие множества — это проблема нахождения бесконфликтного подмножества O , которое является покрытием P. Баник, Панолан, Раман, Сахлот и Саураб ^[5] доказывают следующее для особого случая, в котором конфликтный граф имеет ограниченную древесность :

• Если задача геометрического покрытия является разрешимой с фиксированными параметрами (FPT), то бесконфликтная задача геометрического покрытия является FPT.
• Если задача геометрического покрытия допускает алгоритм r-аппроксимации, то задача геометрического покрытия без конфликтов допускает аналогичный алгоритм аппроксимации за время FPT.

Ссылки

1. Вазирани, Виджай В. (2001). Алгоритмы аппроксимации . Спрингер-Верлаг. ISBN 3-540-65367-8.^{: 112}
2. Дуек-Пинкович, Й., Бен-Гал, И. и Равив, Т. (2022). «Проблема сбора стохастических тестов: модели, точные и эвристические подходы к решению» (PDF) . Европейский журнал операционных исследований, 299 (2022), 945–959}.{{cite web}}: CS1 maint: multiple names: authors list (link) CS1 maint: numeric names: authors list (link)
3. Аркин, Эстер М.; Баник, Аритра; Карми, Пас; Цитовский, Гуи; Кац, Мэтью Дж.; Митчелл, Джозеф СБ; Симаков, Марина (2018-12-11). «Выбор и покрытие цветных точек». Дискретная прикладная математика . 250 : 75–86. doi : 10.1016/j.dam.2018.05.011 . ISSN  0166-218X.
4. Баник, Аритра; Сахлот, Вибха; Саурабх, Сакет (2020-08-01). «Алгоритмы аппроксимации для геометрических задач бесконфликтного покрытия». Computational Geometry . 89 : 101591. doi : 10.1016/j.comgeo.2019.101591. ISSN  0925-7721. S2CID  209959954.
5. Баник, Аритра; Панолан, Фахад; Раман, Венкатеш; Сахлот, Вибха; Саураб, Сакет (01 января 2020 г.). «Параметризованная сложность конфликтных задач геометрического покрытия». Алгоритмика . 82 (1): 1–19. doi : 10.1007/s00453-019-00600-w. ISSN  1432-0541. S2CID  254027914.