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

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

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

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

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

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

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

Формулировка ПДОДИ

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

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

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

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

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

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

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

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

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

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

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

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

${\ displaystyle y_ {j} \ in \ {0,1 \}}$; (если то накрывается)${\ displaystyle y_ {j} = 1}$${\ displaystyle e_ {j}}$

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

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

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

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

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

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

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

${\ displaystyle y_ {j} \ in \ {0,1 \}}$; (если то накрывается)${\ displaystyle y_ {j} = 1}$${\ displaystyle e_ {j}}$

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

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

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

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

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

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

${\ Displaystyle \ сумма _ {я} y_ {ij} \ leq 1}$; (элемент может быть покрыт не более чем одним набором).${\ displaystyle e_ {j} = 1}$

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

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

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

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

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

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

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

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

Примечания

использованная литература

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

внешние ссылки