Проблема максимального покрытия

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

В качестве входных данных вам даны несколько наборов и число $k$. Наборы могут иметь некоторые общие элементы. Вы должны выбрать максимум $k$ из этих наборов так, чтобы охватить максимальное количество элементов, т.е. объединение выбранных множеств имеет максимальный размер.

Формально (невзвешенное) Максимальное покрытие

Экземпляр: число $k$ и коллекция наборов $S=\{S_{1},S_{2},\ldots ,S_{m}\}$.

Цель: найти подмножество. $S'\subseteq S$ наборов, таких, что $\left|S'\right|\leq k$ и количество покрытых элементов $\left|\bigcup _{S_{i}\in S'}{S_{i}}\right|$ максимизируется.

Задача максимального покрытия NP-трудна и может быть аппроксимирована в пределах $1-{\frac {1}{e}}+o(1)\approx 0.632$ при стандартных предположениях. Этот результат по существу соответствует коэффициенту аппроксимации, достигнутому с помощью общего жадного алгоритма, используемого для максимизации субмодулярных функций с ограничением мощности .

формулировка ILP

Задачу максимального покрытия можно сформулировать в виде следующей целочисленной линейной программы .

максимизировать	$\sum _{e_{j}\in E}y_{j}$	(максимизация суммы покрытых элементов)
при условии	$\sum {x_{i}}\leq k$	(не более $k$ наборы выбраны)
	$\sum _{e_{j}\in S_{i}}x_{i}\geq y_{j}$	(если $y_{j}>0$ тогда хотя бы один набор $e_{j}\in S_{i}$ выбрано)
	$y_{j}\in \{0,1\}$	(если $y_{j}=1$ затем $e_{j}$ покрыто)
	$x_{i}\in \{0,1\}$	(если $x_{i}=1$ затем $S_{i}$ выбран для обложки)

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

Жадный алгоритм максимального покрытия выбирает множества по одному правилу: на каждом этапе выбирают множество, содержащее наибольшее количество непокрытых элементов. Можно показать, что этот алгоритм достигает коэффициента аппроксимации $1-{\frac {1}{e}}$. Результаты ln-аппроксимируемости показывают, что жадный алгоритм по сути является наилучшим из возможных алгоритмов полиномиальной аппроксимации для максимального покрытия, если только $P=NP$.

Известные расширения

Результаты о неаппроксимируемости применимы ко всем расширениям проблемы максимального покрытия, поскольку они рассматривают проблему максимального покрытия как особый случай.

Задача максимального покрытия может быть применена к дорожно-транспортным ситуациям; Одним из таких примеров является выбор того, какие автобусные маршруты в сети общественного транспорта следует оборудовать детекторами выбоин, чтобы максимизировать охват, когда доступно только ограниченное количество датчиков. Эта проблема является известным расширением проблемы максимального покрытия и впервые была исследована в литературе Джунаде Али и Владимиром Дьо.

Взвешенная версия

В взвешенной версии каждый элемент $e_{j}$ имеет вес $w(e_{j})$. Задача состоит в том, чтобы найти максимальное покрытие, имеющее максимальный вес. Базовая версия представляет собой особый случай, когда все веса $1$.

максимизировать $\sum _{e\in E}w(e_{j})\cdot y_{j}$. (максимизация взвешенной суммы покрытых элементов).

при условии $\sum {x_{i}}\leq k$; (не более $k$ наборы выбраны).

$\sum _{e_{j}\in S_{i}}x_{i}\geq y_{j}$; (если $y_{j}>0$ тогда хотя бы один набор $e_{j}\in S_{i}$ выбран).

$y_{j}\in \{0,1\}$; (если $y_{j}=1$ затем $e_{j}$ покрыто)

$x_{i}\in \{0,1\}$ (если $x_{i}=1$ затем $S_{i}$ выбран для обложки).

Жадный алгоритм взвешенного максимального покрытия на каждом этапе выбирает набор, содержащий максимальный вес непокрытых элементов. Этот алгоритм достигает коэффициента аппроксимации $1-{\frac {1}{e}}$.

Запланированный максимальный охват

В бюджетной версии максимального покрытия не только каждый элемент $e_{j}$ иметь вес $w(e_{j})$, но и каждый набор $S_{i}$ имеет стоимость $c(S_{i})$. Вместо $k$ что ограничивает количество наборов в рамках бюджета $B$ дано. Этот бюджет $B$ ограничивает общую стоимость покрытия, которое можно выбрать.

максимизировать $\sum _{e\in E}w(e_{j})\cdot y_{j}$. (максимизация взвешенной суммы покрытых элементов).

при условии $\sum {c(S_{i})\cdot x_{i}}\leq B$; (стоимость выбранных наборов не может превышать $B$).

$\sum _{e_{j}\in S_{i}}x_{i}\geq y_{j}$; (если $y_{j}>0$ тогда хотя бы один набор $e_{j}\in S_{i}$ выбран).

$y_{j}\in \{0,1\}$; (если $y_{j}=1$ затем $e_{j}$ покрыто)

$x_{i}\in \{0,1\}$ (если $x_{i}=1$ затем $S_{i}$ выбран для обложки).

Жадный алгоритм больше не будет давать решения с гарантией производительности. А именно, поведение этого алгоритма в худшем случае может быть очень далеко от оптимального решения. Алгоритм аппроксимации расширяется следующим образом. Сначала определим модифицированный жадный алгоритм, который выбирает множество $S_{i}$ который имеет наилучшее соотношение взвешенных непокрытых элементов и стоимости. Во-вторых, среди покрытий мощности $1,2,...,k-1$, найдите лучший чехол, не нарушающий бюджет. Назовите это покрытие $H_{1}$. В-третьих, найдите все покрытия мощности. $k$ которые не нарушают бюджет. Использование этих покрытий мощности $k$ в качестве отправной точки примените модифицированный жадный алгоритм, сохраняя лучшее найденное на данный момент укрытие. Назовите это покрытие $H_{2}$. В конце процесса приблизительным лучшим покрытием будет либо $H_{1}$ или $H_{2}$. Этот алгоритм достигает коэффициента аппроксимации $1-{1 \over e}$ для значений $k\geq 3$. Это наилучший возможный коэффициент аппроксимации, если только $NP\subseteq DTIME(n^{O(\log \log n)})$.

Обобщенный максимальный охват

В обобщенной версии максимального покрытия каждый набор $S_{i}$ имеет стоимость $c(S_{i})$, элемент $e_{j}$ имеет различный вес и стоимость в зависимости от того, в какой комплект он входит.А именно, если $e_{j}$ покрыт набором $S_{i}$ вес $e_{j}$является $w_{i}(e_{j})$ и его стоимость $c_{i}(e_{j})$. Бюджет $B$ указывается общая стоимость решения.

максимизировать $\sum _{e\in E,S_{i}}w_{i}(e_{j})\cdot y_{ij}$. (максимизация взвешенной суммы покрытых элементов в множествах, в которых они покрыты).

при условии $\sum {c_{i}(e_{j})\cdot y_{ij}}+\sum {c(S_{i})\cdot x_{i}}\leq B$; (стоимость выбранных наборов не может превышать $B$).

$\sum _{i}y_{ij}\leq 1$; (элемент $e_{j}=1$ может быть охвачено не более чем одним набором).

$\sum _{S_{i}}x_{i}\geq y_{ij}$; (если $y_{j}>0$ тогда хотя бы один набор $e_{j}\in S_{i}$ выбран).

$y_{ij}\in \{0,1\}$; (если $y_{ij}=1$ затем $e_{j}$ покрыт набором $S_{i}$)

$x_{i}\in \{0,1\}$ (если $x_{i}=1$ затем $S_{i}$ выбран для обложки).

Обобщенный алгоритм максимального покрытия

Алгоритм использует концепцию остаточной стоимости/веса. Остаточная стоимость/вес измеряется относительно предварительного решения и представляет собой разницу стоимости/веса от стоимости/веса, полученного при использовании предварительного решения.

Алгоритм имеет несколько этапов. Сначала найдите решение, используя жадный алгоритм. На каждой итерации жадного алгоритма к предварительному решению добавляется набор, содержащий максимальный остаточный вес элементов, деленный на остаточную стоимость этих элементов вместе с остаточной стоимостью набора. Во-вторых, сравните решение, полученное на первом этапе, с лучшим решением, использующим небольшое количество наборов. В-третьих, вернуть лучшее из всех рассмотренных решений. Этот алгоритм достигает коэффициента аппроксимации $1-1/e-o(1)$.

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

• Проблема покрытия множеств состоит в том, чтобы покрыть все элементы как можно меньшим количеством наборов.

Ссылки

• Vazirani, Vijay V. (2001). Approximation Algorithms . Springer-Verlag. ISBN  978-3-540-65367-7 .