K-аппроксимация k-ударного множества - K-approximation of k-hitting set

В Информатика, k-аппроксимация k-ударного множества является алгоритм аппроксимации для взвешенных ударная установка. Вход - это коллекция S из подмножества какой-то вселенной Т и отображение W из Т к неотрицательным числам, называемым весами элементов Т. В k-ударный набор размер наборов в S не может быть больше чем k. То есть, ${displaystyle forall iin S: | i | leq k}$. Проблема в том, чтобы выбрать какое-то подмножество Т' из Т так что каждый набор в S содержит некоторый элемент Т', и такой, что общий вес всех элементов в Т'как можно меньше.

Алгоритм

Для каждого набора ${displaystyle j}$ в S поддерживается цена, ${displaystyle p_ {j}}$, который изначально равен 0. Для элемента а в Т, позволять S(а) - набор множеств из S содержащий а. В ходе алгоритма сохраняется следующий инвариант

${displaystyle forall ain T: sum _ {jin S (a)} p_ {j} leq W (a).,}$

Мы говорим, что элемент, а, из Т является в обтяжку если ${displaystyle Sigma _ {jin S (a)} p_ {j} = W (a)}$. Основная часть алгоритма состоит из цикла: пока есть набор в S который не содержит элементов из Т что жестко, цена этого набора увеличивается максимально, не нарушая инварианта выше. Когда этот цикл завершается, все наборы содержат некоторый жесткий элемент. Подберите все узкие элементы, которые станут отличным набором.

Правильность

Алгоритм всегда завершается, потому что на каждой итерации цикла цена некоторого набора в S увеличивается достаточно, чтобы сделать еще один элемент из Т в обтяжку. Если он не может увеличить цену, он выходит. Он выполняется за полиномиальное время, потому что цикл не будет делать больше итераций, чем количество элементов в объединении всех наборов S. Он возвращает набор совпадений, потому что при выходе из цикла все наборы S содержать жесткий элемент из Т, и возвращается набор этих плотных элементов.

Обратите внимание, что для любого набора ударов Т * и любые цены ${displaystyle p_ {1}, ldots, p_ {| S |}}$ где инвариант из алгоритма истинен, общий вес набора совпадений является верхним пределом суммы по всем членам Т * суммы цен наборов, содержащих этот элемент, то есть: ${displaystyle Sigma _ {ain T ^ {*}} Sigma _ {jin S (a)} p_ {j} leq Sigma _ {ain T ^ {*}} W (a)}$. Это следует из свойства инвариантности. Кроме того, поскольку цена каждого набора должна встречаться хотя бы один раз в левой части, мы получаем ${displaystyle Sigma _ {jin S} p_ {j} leq Sigma _ {ain T ^ {*}} W (a)}$. Особенно это свойство верно для оптимального набора ударов.

Далее, для набора ударов ЧАС возвращается из алгоритма выше, мы имеем ${displaystyle Sigma _ {ain H} Sigma _ {jin S (a)} p_ {j} = Sigma _ {ain H} W (a)}$. С любой ценой ${displaystyle p_ {j}}$ может появиться самое большее k раз в левой части (поскольку подмножества S может содержать не более чем k элемент из Т) мы получили ${displaystyle Sigma _ {ain H} W (a) leq kcdot Sigma _ {jin S} p_ {j}}$ В сочетании с предыдущим абзацем получаем ${displaystyle Sigma _ {ain H} W (a) leq kcdot Sigma _ {ain T ^ {*}} W (a)}$, куда Т * является оптимальным набором ударов. Это как раз гарантия того, что это алгоритм k-приближения.

Отношение к линейному программированию

Этот алгоритм является примером первично-дуальный метод, также называемый метод ценообразования. Интуиция подсказывает, что это двойной к линейное программирование алгоритм. Для объяснения см. http://algo.inria.fr/seminars/sem00-01/vazirani.html.

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

• Клейнберг, Дж.; Тардос, Э. (2006). Разработка алгоритма. ISBN  0-321-29535-8..
• Семь; Р. Бар-Иегуда (1981). «Алгоритм линейной аппроксимации для задачи взвешенного вершинного покрытия». J. Алгоритмы. 2 (2): 198–203. Дои:10.1016/0196-6774(81)90020-1.
• Гоэманс, М. X.; Уильямсон, Д. П. (1997). «Прямо-дуальный метод для алгоритмов аппроксимации и его применение к задачам проектирования сетей». В Хохбаум, Дорит С. (ред.). Аппроксимационные алгоритмы для NP-сложных задач. Издательская компания PWS. ISBN  0-534-94968-1..