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

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

Наиболее яркими примерами покрывающих проблем являются установить проблему прикрытия, что эквивалентно проблема с набором, и его частные случаи, проблема покрытия вершины и проблема с краевым покрытием.

Пары покрытие / упаковка-проблема
Покрытие проблем Проблемы с упаковкой Крышка минимального набора Максимальный набор упаковки Минимальное покрытие вершины Максимальное соответствие Минимальное краевое покрытие Максимальный независимый набор Крышка бункера Бин упаковка

Общий состав LP

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

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

Такая целочисленная линейная программа называется проблема покрытия если ${ displaystyle a_ {ij}, 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 А mathbf {х} geq mathbf {b}}$ довольны, говорят, что ${ displaystyle mathbf {x}}$ это покрытие (покрываемые структуры зависят от комбинаторного контекста). Наконец, оптимальным решением указанной выше целочисленной линейной программы является покрытие с минимальными затратами.

Другое использование

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

Смотрите также

• В проблема покрытия края biclique просит покрыть все ребра данного графа (как можно меньше) полные двудольные подграфы.
• Проблема покрытия диска, проблема покрытия единичного круга меньшими кругами
• Полигональное покрытие, проблема покрытия сложного многоугольника более простыми многоугольниками, такими как квадраты или прямоугольники.
• Проблема непрямоугольника. Проблема покрытия прямоугольной области без подпрямоугольников. ^[2]

Примечания

Рекомендации

• Вазирани, Виджай В. (2001). Алгоритмы аппроксимации. Springer-Verlag. ISBN  3-540-65367-8.

внешняя ссылка

• Центр упаковки Эриха содержит некоторые иллюстрации задач геометрического покрытия.