Освещение проблем

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

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

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

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

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

минимизировать	$\sum _{i=1}^{n}c_{i}x_{i}$
при условии	$\sum _{i=1}^{n}a_{ji}x_{i}\geq b_{j}{\text{ for }}j=1,\dots ,m$
	$x_{i}\in \left\{0,1,2,\ldots \right\}{\text{ for }}i=1,\dots ,n$ .

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

Интуиция: предположим, что у вас есть $n$ типы объектов и каждый объект типа $i$ имеет соответствующую стоимость $c_{i}$ . Число $x_{i}$ указывает, сколько объектов типа $i$ Мы покупаем. Если ограничения $A\mathbf {x} \geq \mathbf {b}$ довольны, говорят, что $\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 называется бесконфликтным, оно является независимым множеством в GO _, то есть никакие два объекта в Q не соединены ребром в GO _если .
Радужный набор — это бесконфликтный набор в особом случае, когда G _O состоит из непересекающихся клик, где каждая клика представляет цвет.

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

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

Ссылки

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

[1] Vazirani, Vijay V. (2001). Approximation Algorithms . Springer-Verlag. ISBN 3-540-65367-8 . ^: 112

[2] Дуек-Пинкович Ю., Бен-Гал И. и Равив Т. (2022). «Проблема сбора стохастических тестов: модели, точные и эвристические подходы к решению» (PDF) . Европейский журнал операционных исследований, 299 (2022), 945–959}. {{cite web}}: CS1 maint: несколько имен: список авторов ( ссылка ) CS1 maint: числовые имена: список авторов ( ссылка )

[3] Аркин, Эстер М.; Баник, Аритра; Карми, Пас; Цитовский, Ги; Кац, Мэтью Дж.; Митчелл, Джозеф С.Б.; Симаков, Марина (11 декабря 2018 г.). «Выделение и закрытие цветных точек» . Дискретная прикладная математика . 250 : 75–86. дои : 10.1016/j.dam.2018.05.011 . ISSN 0166-218X .

[4] Баник, Аритра; Сахлот, Вибха; Саураб, Сакет (01 августа 2020 г.). «Аппроксимационные алгоритмы решения геометрических задач бесконфликтного покрытия» . Вычислительная геометрия . 89 : 101591. doi : 10.1016/j.comgeo.2019.101591 . ISSN 0925-7721 . S2CID 209959954 .

[5] Баник, Аритра; Панолан, Фахад; Раман, Венкатеш; Сахлот, Вибха; Саураб, Сакет (01 января 2020 г.). «Параметризованная сложность геометрических задач о покрытии, имеющих конфликты» . Алгоритмика . 82 (1): 1–19. дои : 10.1007/s00453-019-00600-w . ISSN 1432-0541 . S2CID 254027914 .

[1]

[2]

[3]

[4]

[5]