Analýza nadvlády - Domination analysis

Analýza nadvlády z aproximační algoritmus je způsob, jak odhadnout jeho výkon, který představili Glover a Punnen v roce 1997. Na rozdíl od klasického přibližný poměr Analýza, která porovnává numerickou kvalitu vypočítaného řešení s kvalitou optimálního řešení, zahrnuje analýza dominance zkoumání pořadí vypočítaného řešení v seřazeném pořadí všech možných řešení. V tomto stylu analýzy se říká, že má algoritmus číslo dominance nebo dominantní číslo K., pokud existuje podmnožina K. různá řešení problému, mezi nimiž je výstup algoritmu nejlepší. Analýza dominance může být také vyjádřena pomocí a poměr nadvlády, což je zlomek prostoru řešení, který není o nic lepší než dané řešení; toto číslo vždy leží v intervalu [0,1], přičemž větší čísla označují lepší řešení. Analýza nadvlády se nejčastěji používá u problémů, u nichž je znám celkový počet možných řešení a u nichž je přesné řešení obtížné.

Například v Problém obchodního cestujícího, existují (n-1)! možná řešení problémové instance s n města. Pokud lze prokázat, že algoritmus má číslo dominance blízké (n-1)!, Nebo ekvivalentně, aby měl poměr dominance blízký 1, pak to lze považovat za výhodnější než algoritmus s nižším počtem dominancí.

Pokud je to možné efektivně najít náhodné vzorky prostoru řešení problému, jak je tomu v problému Traveling salesman, pak je to pro a randomizovaný algoritmus najít řešení, které s vysokou pravděpodobností má vysoký poměr dominance: jednoduše sestavte sadu vzorků a vyberte z nich nejlepší řešení. (Viz např. Orlin a Sharma.)

Zde popsané číslo dominance by nemělo být zaměňováno s číslem dominance grafu, který odkazuje na počet vrcholů v nejmenším dominující sada grafu.

V poslední době se objevil rostoucí počet článků, ve kterých byla k posouzení výkonnosti heuristiky použita analýza dominance. Tento druh analýzy lze považovat za konkurenční s klasickou tradicí analýzy poměru přiblížení. Na obě opatření lze pohlížet jako na doplňková.

Známé výsledky

Tato část obsahuje technický přehled známých výsledků.

Vrcholový kryt

 Nepřibližnost. Nechť ε> 0. Pokud P = NP, neexistuje žádný polynomiální algoritmus pro Vertex Cover, takže jeho číslo dominance je větší než 3 ^ ((n-n ^ ε) / 3).

Batoh

 Nepřibližnost. Nechť ε> 0. Pokud P = NP, neexistuje pro Knapsack žádný polynomiální algoritmus, takže jeho dominantní číslo je větší než 2 ^ (n-n ^ ε).

Maximální uspokojivost

TSP

Reference

• Glover, F. a Punnen, A. P. (1997). "Problém obchodního cestujícího: nové řešitelné případy a vazby na vývoj aproximačních algoritmů". J. Oper. Res. Soc. 48 (5): 502–510. doi:10.1057 / palgrave.jors.2600392.CS1 maint: více jmen: seznam autorů (odkaz)
• Gutin, Gregory a Yeo, Anders (2004). „Úvod do analýzy nadvlády“ (PDF). Optimalizace online. Externí odkaz v | vydavatel = (Pomoc)CS1 maint: více jmen: seznam autorů (odkaz)
• Orlin, James B. a Sharma, Dushyant (2002). „Rozšířené sousedství: definice a charakteristika“ (PDF).CS1 maint: více jmen: seznam autorů (odkaz)