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

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

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

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

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

свести к минимуму	${\ Displaystyle \ сумма _ {я = 1} ^ {п} с_ {я} х_ {я}}$
при условии	${\ displaystyle \ sum _ {i = 1} ^ {n} a_ {ji} x_ {i} \ geq b_ {j} {\ text {for}} j = 1, \ dots, m}$
	${\ displaystyle x_ {i} \ geq 0 {\ text {for}} i = 1, \ dots, n}$.

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

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

Виды покрытия проблем [ править ]

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

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

Радужное покрытие и бесконфликтное покрытие [ править ]

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

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

Задача NP-сложная (редукцией с линейного SAT ).

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

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

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

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

Ссылки [ править ]