k-аппроксимация набора k-попаданий

В информатике — k-аппроксимация набора k-попаданий это алгоритм аппроксимации взвешенного набора попаданий . Входные данные представляют собой набор S подмножеств в неотрицательные числа , некоторой вселенной T и отображение W из T называемые весами элементов T . В наборе k-попадания размер наборов в S не может быть больше k . То есть, $\forall i\in S:|i|\leq k$. Теперь проблема состоит в том, чтобы выбрать такое подмножество T ' из T , чтобы каждое множество в S содержало некоторый элемент из T ' и чтобы общий вес всех элементов в T ' был как можно меньшим.

Алгоритм

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

$\forall a\in T:\sum _{j\in S(a)}p_{j}\leq W(a).\,$

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

Корректность

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

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

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

Связь с линейным программированием

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

Ссылки

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