K-aproximace sady úderů k - K-approximation of k-hitting set

v počítačová věda, k-aproximace k-bít množiny je aproximační algoritmus pro vážené bít set. Vstup je a sbírka S z podmnožiny nějakého vesmíru T a a mapování Ž z T na nezáporná čísla, která se nazývají váhy prvků T. v k-bít set velikost sad v S nemůže být větší než k. To znamená, ${displaystyle forall iin S: | i | leq k}$ . Nyní je problém vybrat nějakou podmnožinu T'z T tak, že každý vstup S obsahuje nějaký prvek z T"a taková, že celková hmotnost všech prvků v T„je co nejmenší.

Algoritmus

Pro každou sadu ${displaystyle j}$ v S je udržován a cena, ${displaystyle p_ {j}}$ , což je zpočátku 0. Pro prvek A v T, nechť S(A) být sbírkou sad z S obsahující A. Během algoritmu je zachován následující invariant

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

Říkáme, že prvek, A, z T je těsný -li ${displaystyle Sigma _ {jin S (a)} p_ {j} = W (a)}$ . Hlavní část algoritmu se skládá ze smyčky: Dokud je nastaven vstup S který neobsahuje žádný prvek z T což je těsné, cena této sady se zvýší co nejvíce, aniž by došlo k porušení výše uvedeného invariantu. Když tato smyčka skončí, všechny sady obsahují nějaký těsný prvek. Vyberte všechny těsné prvky, které mají být údernou sadou.

Správnost

Algoritmus vždy končí, protože v každé iteraci smyčky je cena nějakého nastavena S je dostatečně zvětšen, aby se z něj vytvořil ještě jeden prvek T těsný. Pokud nemůže zvýšit žádnou cenu, opustí se. Spouští se v polynomiálním čase, protože smyčka neprovede více iterací, než je počet prvků ve spojení všech sad S. Vrátí úderovou sadu, protože když smyčka skončí, všechny sady se vrátí S obsahují těsný prvek z Ta sada těchto těsných prvků se vrátí.

Všimněte si, že pro každou zasaženou sadu T * a případné ceny ${displaystyle p_ {1}, ldots, p_ {| S |}}$ kde je invariant z algoritmu pravdivý, je celková váha sady úderů horní limit součtu přes všechny členy T * ze součtu cen sad obsahujících tento prvek, tedy: ${displaystyle Sigma _ {ain T ^ {*}} Sigma _ {jin S (a)} p_ {j} leq Sigma _ {ain T ^ {*}} W (a)}$ . To vyplývá z invariantní vlastnosti. Dále, protože cena každé sady se musí alespoň jednou objevit na levé straně, dostaneme ${displaystyle Sigma _ {jin S} p_ {j} leq Sigma _ {ain T ^ {*}} W (a)}$ . Zvláště tato vlastnost platí pro optimální sadu úderů.

Dále pro úderovou sadu H vrátili jsme se z výše uvedeného algoritmu ${displaystyle Sigma _ {ain H} Sigma _ {jin S (a)} p_ {j} = Sigma _ {ain H} W (a)}$ . Od jakékoli ceny ${displaystyle p_ {j}}$ se může objevit maximálně k krát na levé straně (od podmnožin S nesmí obsahovat více než k prvek z T) dostaneme ${displaystyle Sigma _ {ain H} W (a) leq kcdot Sigma _ {jin S} p_ {j}}$ V kombinaci s předchozím odstavcem dostaneme ${displaystyle Sigma _ {ain H} W (a) leq kcdot Sigma _ {ain T ^ {*}} W (a)}$ , kde T * je optimální sada úderů. To je přesně záruka, že se jedná o algoritmus k-aproximace.

Vztah k lineárnímu programování

Tento algoritmus je instancí metoda primal-dual, také zvaný způsob stanovení cen. Intuice je, že je dvojí do a lineární programování algoritmus. Vysvětlení viz http://algo.inria.fr/seminars/sem00-01/vazirani.html.

Reference

Kleinberg, J.; Tardos, E. (2006). Návrh algoritmu. ISBN 0-321-29535-8..
S. Dokonce; R. Bar-Jehuda (1981). „Algoritmus aproximace lineárního času pro problém váženého vrcholového krytu“. J. Algoritmy. 2 (2): 198–203. doi:10.1016/0196-6774(81)90020-1.
Goemans, M. X.; Williamson, D. P. (1997). "Metoda primal-dual pro aproximační algoritmy a její aplikace na problémy návrhu sítě". v Hochbaum, Dorit S. (vyd.). Aproximační algoritmy pro NP-těžké problémy. Nakladatelská společnost PWS. ISBN 0-534-94968-1..