Approximationsalgoritm - Approximation algorithm

I datavetenskap och forskningsverksamhet , approximationsalgoritmer är effektiva algoritmer som finner ungefärliga lösningar på optimeringsproblem (särskilt NP-svåra problem) med bevisbara garantier på avståndet mellan åter lösningen till den optimala. Approximeringsalgoritmer uppstår naturligtvis inom teoretisk datavetenskap som en följd av den allmänt trodde P ≠ NP -gissningen. Under denna gissning kan en bred klass av optimeringsproblem inte lösas exakt under polynomtid . Området approximationsalgoritmer försöker därför förstå hur nära det är möjligt att närma sig optimala lösningar på sådana problem under polynomtid. I en överväldigande majoritet av fallen är garantin för sådana algoritmer en multiplikativ som uttrycks som ett approximationsförhållande eller approximationsfaktor, dvs den optimala lösningen är alltid garanterad att ligga inom en (förutbestämd) multiplikationsfaktor för den returnerade lösningen. Det finns dock också många approximationsalgoritmer som ger en additiv garanti för kvaliteten på den returnerade lösningen. Ett anmärkningsvärt exempel på en approximationsalgoritm som ger båda är den klassiska approximationsalgoritmen för Lenstra , Shmoys och Tardos för schemaläggning på orelaterade parallella maskiner .

Utformningen och analysen av approximationsalgoritmer innebär väsentligt ett matematiskt bevis som certifierar kvaliteten på de returnerade lösningarna i värsta fall. Detta skiljer dem från heuristik som glödgning eller genetiska algoritmer , som hittar någorlunda bra lösningar på vissa ingångar, men ger ingen tydlig indikation från början när de kan lyckas eller misslyckas.

Det finns ett stort intresse för teoretisk datavetenskap för att bättre förstå vilka gränser vi kan närma oss vissa kända optimeringsproblem. Till exempel är en av de långa öppna frågorna inom datavetenskap att avgöra om det finns en algoritm som överträffar 1,5-approximationsalgoritmen för Christofides till det metriska resande säljarproblemet . Lusten att förstå hårda optimeringsproblem ur tillnärmningsperspektivet motiveras av upptäckten av överraskande matematiska kopplingar och allmänt tillämpliga tekniker för att designa algoritmer för hårda optimeringsproblem. Ett välkänt exempel på det förra är Goemans – Williamson-algoritmen för maximal skärning , som löser ett grafteoretiskt problem med hjälp av högdimensionell geometri.

Introduktion

Ett enkelt exempel på en approximationsalgoritm är ett för det minsta toppunktsproblemet , där målet är att välja den minsta uppsättningen hörn så att varje kant i inmatningsgrafen innehåller minst en vald toppunkt. Ett sätt att hitta en vertex -kåpa är att upprepa följande process: hitta en otäckt kant, lägg till båda dess slutpunkter i locket och ta bort alla kanter som infaller i endera hörnet från grafen. Eftersom varje hörnhölje i inmatningsdiagrammet måste använda ett distinkt hörn för att täcka varje kant som övervägdes i processen (eftersom det bildar en matchning ) är det framställda hörnhöljet högst dubbelt så stort som det optimala. Med andra ord är detta en algoritm för approximation av konstant faktor med en approximationsfaktor på 2. Under de senaste unika speluppfattningarna är denna faktor till och med den bästa möjliga.

NP-hårda problem varierar mycket när det gäller tillnärmning; vissa, såsom ryggsäckproblemet , kan approximeras inom en multiplikativ faktor för alla fasta och producerar därför lösningar godtyckligt nära det optimala (en sådan familj av approximationsalgoritmer kallas ett schema för polynomtids -approximation eller PTAS). Andra är omöjliga att approximera inom någon konstant eller till och med polynom faktor om inte P = NP , som i fallet med det maximala klickproblemet . Därför är en viktig fördel med att studera approximationsalgoritmer en finkornig klassificering av svårigheterna med olika NP-hårda problem utöver den som teorin om NP-fullständighet ger . Med andra ord, även om NP-kompletta problem kan vara likvärdiga (under polynomiska tidsförkortningar) med varandra ur perspektivet på exakta lösningar, beter sig motsvarande optimeringsproblem mycket annorlunda ur perspektivet av ungefärliga lösningar. ${\ displaystyle 1+ \ epsilon}$${\ displaystyle \ epsilon> 0}$

Algoritmdesigntekniker

Nu finns det flera etablerade tekniker för att designa approximationsalgoritmer. Dessa inkluderar följande.

1. Girig algoritm
2. Lokal sökning
3. Uppräkning och dynamisk programmering
4. Löser en konvex programmeringsavslappning för att få en fraktionell lösning. Omvandla sedan denna fraktionerade lösning till en genomförbar lösning med någon lämplig avrundning. De populära avslappningarna inkluderar följande.
   • Linjär programmering lättnader
   • Semidefinite programmering relaxations
5. Primal-dubbla metoder
6. Dubbel passform
7. Bädda in problemet i vissa mätvärden och sedan lösa problemet på mätvärdet. Detta är också känt som metrisk inbäddning.
8. Slumpmässig provtagning och användning av slumpmässighet i allmänhet i samband med metoderna ovan.

A posteriori garantier

Medan approximationsalgoritmer alltid ger en a priori worst case -garanti (vare sig det är additiv eller multiplikativ), ger de i vissa fall också en a posteriori -garanti som ofta är mycket bättre. Detta är ofta fallet för algoritmer som fungerar genom att lösa en konvex avslappning av optimeringsproblemet på den angivna ingången. Till exempel finns det en annan approximationsalgoritm för minsta toppunktskydd som löser en linjär programmeringsavslappning för att hitta en toppunktskydd som är högst dubbelt så hög som värdet av avspänningen. Eftersom avslappningens värde aldrig är större än storleken på det optimala vertex-locket ger detta ytterligare en 2-approximationsalgoritm. Även om detta liknar a priori -garantin för den tidigare approximationsalgoritmen, kan garantin för den senare vara mycket bättre (faktiskt när värdet av LP -avslappningen är långt ifrån storleken på det optimala toppunktskyddet).

Approximationens hårdhet

Approximationsalgoritmer som forskningsområde är nära besläktade med och informeras av inapproximability-teori där icke-existens av effektiva algoritmer med vissa approximationsförhållanden bevisas (betingat av allmänt trodde hypoteser som P ≠ NP-gissningen) med hjälp av reduktioner . När det gäller det metriska resande säljarproblemet utesluter det mest kända inapproximabilitetsresultatet algoritmer med ett approximationsförhållande mindre än 123/122 ≈ 1.008196 om inte P = NP, Karpinski, Lampis, Schmied. Tillsammans med kunskapen om förekomsten av Christofides 1,5 approximationsalgoritm, säger detta att tröskeln för approximativitet för metrisk resande säljare (om den finns) ligger någonstans mellan 123/122 och 1,5.

Även om resultaten av olämplighet har bevisats sedan 1970 -talet, uppnåddes sådana resultat med hjälp av ad hoc -medel och ingen systematisk förståelse var tillgänglig vid den tiden. Det är först sedan 1990 års resultat av Feige, Goldwasser, Lovász, Safra och Szegedy om Oberoende uppsättningar och det berömda PCP -teorins inapproximibilitet , som moderna verktyg för att bevisa olämpliga resultat avslöjades. PCP -satsen visar till exempel att Johnsons approximationsalgoritmer från 1974 för Max SAT , uppsättningsomslag , oberoende uppsättning och färgning alla uppnår det optimala approximationsförhållandet, förutsatt att P ≠ NP.

Praktiskhet

Alla approximationsalgoritmer är inte lämpliga för direkta praktiska tillämpningar. Vissa handlar om att lösa icke-trivial linjär programmering / semidefinite relaxations (som själva kan åberopa ellipsoidalgoritmen ), komplexa datastrukturer eller sofistikerade algoritmiska tekniker, vilket leder till svåra implementeringsproblem eller förbättrad körtidsprestanda (över exakta algoritmer) endast på opraktiskt stora ingångar . Implementerings- och drifttidsfrågor åt sidan, de garantier som tillhandahålls av approximationsalgoritmer kan i sig inte vara tillräckligt starka för att motivera deras övervägande i praktiken. Trots deras oförmåga att användas "out of the box" i praktiska tillämpningar kan idéerna och insikterna bakom utformningen av sådana algoritmer ofta införlivas på andra sätt i praktiska algoritmer. På detta sätt är studien av även mycket dyra algoritmer inte en helt teoretisk strävan eftersom de kan ge värdefulla insikter.

I andra fall, även om de första resultaten är av rent teoretiskt intresse, med tiden, med en förbättrad förståelse, kan algoritmerna förfinas för att bli mer praktiska. Ett sådant exempel är den inledande PTAS för euklidisk TSP av Sanjeev Arora (och oberoende av Joseph Mitchell ) som hade en oöverkomlig körtid för en approximation. Men inom ett år införlivades dessa idéer i en nära-linjär tidsalgoritm för varje konstant . ${\ displaystyle n^{O (1/\ epsilon)}}$${\ displaystyle 1+ \ epsilon}$${\ displaystyle O (n \ log n)}$${\ displaystyle \ epsilon> 0}$

Prestandagarantier

För vissa approximationsalgoritmer är det möjligt att bevisa vissa egenskaper om approximationen av det optimala resultatet. Till exempel definieras en ρ -approximeringsalgoritm A som en algoritm för vilken det har bevisats att värdet/kostnaden, f ( x ), för den ungefärliga lösningen A ( x ) till en instans x inte kommer att vara mer (eller mindre, beroende på situationen) än en faktor ρ gånger värdet, OPT, för en optimal lösning.

${\ displaystyle {\ begin {cases} \ mathrm {OPT} \ leq f (x) \ leq \ rho \ mathrm {OPT}, \ qquad {\ mbox {if}} \ rho> 1; \\\ rho \ mathrm {OPT} \ leq f (x) \ leq \ mathrm {OPT}, \ qquad {\ mbox {if}} \ rho <1. \ end {cases}}}$

Faktorn ρ kallas den relativa prestandagarantin . En approximationsalgoritm har en absolut prestandagaranti eller begränsat fel c , om det har bevisats för varje instans x det

${\ displaystyle (\ mathrm {OPT} -c) \ leq f (x) \ leq (\ mathrm {OPT} +c).}$

På samma sätt definieras prestandagarantin , R ( x, y ), för en lösning y till en instans x

${\ displaystyle R (x, y) = \ max \ left ({\ frac {OPT} {f (y)}}, {\ frac {f (y)} {OPT}} \ right),}$

där f ( y ) är värdet/kostnaden för lösningen y för instansen x . Det är uppenbart att prestandagarantin är större än eller lika med 1 och lika med 1 om och bara om y är en optimal lösning. Om en algoritm A garanterar att returnera lösningar med en prestandagaranti på högst r ( n ), sägs A vara en r ( n ) -approximeringsalgoritm och har ett approximationsförhållande på r ( n ). På samma sätt sägs ett problem med en r ( n ) -approximeringsalgoritm vara r ( n ) - approximativt eller ha ett approximationsförhållande på r ( n ).

För minimeringsproblem ger de två olika garantierna samma resultat och att för maximeringsproblem motsvarar en relativ prestandagaranti på ρ en prestandagaranti på . I litteraturen är båda definitionerna vanliga men det är klart vilken definition som används eftersom, för maximeringsproblem, som ρ ≤ 1 medan r ≥ 1. ${\ displaystyle r = \ rho ^{-1}}$

Den absoluta prestandagarantin för någon approximationsalgoritm A , där x hänvisar till en instans av ett problem, och där är prestandagarantin för A på x (dvs ρ för probleminstans x ) är: ${\ displaystyle \ mathrm {P} _ {A}}$${\ displaystyle R_ {A} (x)}$

${\ displaystyle \ mathrm {P} _ {A} = \ inf \ {r \ geq 1 \ mitt R_ {A} (x) \ leq r, \ forall x \}.}$

Det vill säga det är den största gränsen på approximationsförhållandet, r , som man ser över alla möjliga fall av problemet. På samma sätt är det asymptotiska prestandaförhållandet : ${\ displaystyle \ mathrm {P} _ {A}}$ ${\ displaystyle R_ {A}^{\ infty}}$

${\ displaystyle R_ {A} ^{\ infty} = \ inf \ {r \ geq 1 \ mid \ existerar n \ i \ mathbb {Z} ^{+}, R_ {A} (x) \ leq r, \ förall x, | x | \ geq n \}.}$

Det vill säga att det är detsamma som det absoluta prestandakvoten , med en nedre gräns n för storleken på probleminstanser. Dessa två typer av förhållanden används eftersom det finns algoritmer där skillnaden mellan dessa två är signifikant.

Prestandagarantier

	r -cirka	ρ -cirka	rel. fel	rel. fel	norm. rel. fel	magmuskler. fel
max: ${\ displaystyle f (x) \ geq}$	${\ displaystyle r^{-1} \ mathrm {OPT}}$	${\ displaystyle \ rho \ mathrm {OPT}}$	${\ displaystyle (1-c) \ mathrm {OPT}}$	${\ displaystyle (1-c) \ mathrm {OPT}}$	${\ displaystyle (1-c) \ mathrm {OPT} +c \ mathrm {WORST}}$	${\ displaystyle \ mathrm {OPT} -c}$
min: ${\ displaystyle f (x) \ leq}$	${\ displaystyle r \ mathrm {OPT}}$	${\ displaystyle \ rho \ mathrm {OPT}}$	${\ displaystyle (1+c) \ mathrm {OPT}}$	${\ displaystyle (1-c)^{-1} \ mathrm {OPT}}$	${\ displaystyle (1-c)^{-1} \ mathrm {OPT} +c \ mathrm {WORST}}$	${\ displaystyle \ mathrm {OPT} +c}$

Epsilon -termer

I litteraturen betyder ett approximationsförhållande för ett problem med maximering (minimering) av c - ϵ (min: c + ϵ) att algoritmen har ett approximationsförhållande på c ∓ ϵ för godtyckligt ϵ> 0 men att förhållandet inte har (eller kan inte) visas för ϵ = 0. Ett exempel på detta är den optimala inapproximibiliteten-inexistensen av approximation-förhållandet 7 /8 + ϵ för tillfredsställande MAX-3SAT- instanser på grund av Johan Håstad . Som nämnts tidigare, när c = 1, sägs att problemet har ett approximationsschema för polynomtid .

En term-term kan dyka upp när en approximationsalgoritm introducerar ett multiplikativt fel och ett konstant fel medan minimioptimum för instanser av storlek n går till oändlighet som n gör. I detta fall är approximationsförhållandet c ∓ k / OPT = c ∓ o (1) för vissa konstanter c och k . Givet godtyckligt ε> 0, kan man välja en tillräckligt stor N sådant att termen k / OPT <ε för varje n ≥ N . För varje fast ϵ kan instanser av storlek n <N lösas med brutal kraft, vilket visar ett approximationsförhållande - förekomst av approximationsalgoritmer med en garanti - på c ∓ ϵ för varje ϵ> 0.

Se även

• Dominansanalys tar hänsyn till garantier när det gäller den beräknade lösningens rang.
• PTAS - en typ av approximationsalgoritm som tar approximationsförhållandet som en parameter
• APX är klassen av problem med någon konstant-faktor approximationsalgoritm
• Approximation-bevarande reduktion
• Exakt algoritm

Citat

Referenser

• Vazirani, Vijay V. (2003). Tillnärmningsalgoritmer . Berlin: Springer. ISBN 978-3-540-65367-7.
• Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest och Clifford Stein . Introduktion till algoritmer , andra upplagan. MIT Press och McGraw-Hill, 2001. ISBN  0-262-03293-7 . Kapitel 35: Approximation Algorithms, s. 1022–1056.
• Dorit S. Hochbaum , red. Approximation Algorithms for NP-Hard problems , PWS Publishing Company, 1997. ISBN  0-534-94968-1 . Kapitel 9: Olika begrepp om approximationer: Bra, bättre, bästa och mer
• Williamson, David P .; Shmoys, David B. (26 april 2011), The Design of Approximation Algorithms , Cambridge University Press , ISBN 978-0521195270

externa länkar

• Pierluigi Crescenzi, Viggo Kann, Magnús Halldórsson, Marek Karpinski och Gerhard Woeginger , A compendium of NP optimization problems .