Fullständigt polynom-tidsapproximationsschema

Ett fullständigt polynom-tidsapproximationsschema (FPTAS) är en algoritm för att hitta ungefärliga lösningar på funktionsproblem , speciellt optimeringsproblem . En FPTAS tar som ingång en instans av problemet och en parameter ε > 0. Den returnerar som utdata ett värde som är minst $1-\epsilon$ gånger det korrekta värdet, och som mest ${\ displaystyle 1+\epsilon }$ gånger det korrekta värdet.

I samband med optimeringsproblem förstås det korrekta värdet som värdet av den optimala lösningen, och det antyds ofta att en FPTAS ska producera en giltig lösning (och inte bara värdet av lösningen). Att returnera ett värde och hitta en lösning med det värdet är likvärdiga förutsatt att problemet har självreducerbarhet .

Viktigt är att körtiden för en FPTAS är polynom i problemstorleken och i 1/ε. Detta står i motsats till ett allmänt polynom-tidsapproximationsschema ( PTAS). Körtiden för en allmän PTAS är polynom i problemstorleken för varje specifik ε, men kan vara exponentiell i 1/ε.

Termen FPTAS kan också användas för att hänvisa till klassen av problem som har en FPTAS. FPTAS är en delmängd av PTAS, och om inte P = NP är det en strikt delmängd.

Relation till andra komplexitetsklasser

Alla problem i FPTAS är lösta med fasta parametrar med avseende på standardparameteriseringen.

Alla starkt NP-hårda optimeringsproblem med en polynomiellt bunden objektivfunktion kan inte ha en FPTAS om inte P=NP. Men det omvända misslyckas: t.ex. om P inte är lika med NP, är ryggsäck med två begränsningar inte starkt NP-hård, men har ingen FPTAS även när det optimala målet är polynomiellt begränsat.

Konvertera ett dynamiskt program till en FPTAS

Woeginger presenterade ett allmänt schema för att konvertera en viss klass av dynamiska program till en FPTAS.

Inmatning

Schemat hanterar optimeringsproblem där ingången definieras enligt följande:

• Inmatningen är gjord av n vektorer, x ₁ ,..., x _n .
• Varje ingångsvektor är gjord av några $a$ icke-negativa heltal, där $a$ kan bero på inmatningen.
• Alla komponenter i ingångsvektorerna är kodade i binärt. Så storleken på problemet är O( n +log( X )), där X är summan av alla komponenter i alla vektorer.

Extremt enkelt dynamiskt program

Det antas att problemet har en dynamisk programmeringsalgoritm (DP) som använder tillstånd . Varje tillstånd är en vektor gjord av några $b$ icke-negativa heltal, där $b$ är oberoende av indata. DP arbetar i n steg. Vid varje steg och _i bearbetar den ingången xi konstruerar en uppsättning tillstånd Si _. Varje tillstånd kodar en partiell lösning på problemet, med hjälp av ingångar x1 , xi _... , _. Komponenterna i DP är:

• ₀ En uppsättning S av initialtillstånd .
• En uppsättning F övergångsfunktioner . Varje funktion f i F mappar ett par (tillstånd, indata) till ett nytt tillstånd.
• En objektiv funktion g, avbildar ett tillstånd till dess värde.

Algoritmen för DP är:

• ₀ Låt S := mängden initialtillstånd.
• För k = 1 till n gör:
  • Låt S _k := { f ( s , x _k ) | f i F , s i Sk _{_ −1} }
• Utgång min/max {g(s) | s i S _n }.

Drifttiden för DP är linjär i antalet möjliga tillstånd. I allmänhet kan detta tal vara exponentiellt i storleken på indataproblemet: det kan vara i O( n V ^b ), där V är det största heltal som kan förekomma i ett tillstånd. Om V är i O( X ), så är körtiden i O( n X ^b ), vilket endast är pseudopolynomtid , eftersom den är exponentiell i problemstorleken som är i O(log X ).

Sättet att göra det polynom är att trimma tillståndsutrymmet : istället för att behålla alla möjliga tillstånd i varje steg, behåll bara en delmängd av tillstånden; ta bort stater som är "tillräckligt nära" andra stater. Under vissa förutsättningar kan denna trimning göras på ett sätt som inte förändrar det objektiva värdet för mycket.

För att formalisera detta antar vi att det aktuella problemet har en icke-negativ heltalsvektor d = ( d ₁ ,..., d _b ), kallad problemets gradvektor . För varje reellt tal r >1 säger vi att två tillståndsvektorer s ₁ , s ₂ är (d,r)-nära om, för varje koordinat j i 1,..., b : $r^{-d_{j}}\cdot s_{1,j}\leq s_{2,j}\leq r^{d_ {j}}\cdot s_{1,j}$ (i synnerhet om d _j =0 för vissa j , då $s_{1,j}=s_{2, j}$ ).

Ett problem kallas extremt välvilligt om det uppfyller följande tre villkor:

1. Närhet bevaras av övergångsfunktionerna : För valfri r >1, för valfri övergångsfunktion f i F , för valfri ingångsvektor x , och för valfri två tillståndsvektorer s ₁ , s ₂ , gäller följande: om s ₁ är ( d,r )-nära s2 ₎ , då är f ( s1 _, x ) ( d,r -nära f ( s2 _, x ) .
   • Ett tillräckligt villkor för detta kan kontrolleras enligt följande. För varje funktion f ( s , x ) i F , och för varje koordinat j i 1,..., b , beteckna med f _j (s,x) den j -te koordinaten för f . Denna f _j kan ses som en heltalsfunktion i b + a -variabler. Antag att varje sådan f _j är ett polynom med icke-negativa koefficienter. Konvertera det till ett polynom av en enda variabel z , genom att ersätta s =(z ^d1 ,...,z ^db ) och x =(1,...,1). Om graden av det resulterande polynomet i z som mest är dj _. , är villkor 1 uppfyllt
2. Närhet bevaras av värdefunktionen : Det finns ett heltal G ≥ 0 (som är en funktion av värdefunktionen g och gradvektorn d ), så att för vilken som helst r >1, och för alla två tillståndsvektorer s ₁ , s2 gäller _följande : om s1 är ( · ^d ,r ) ( ₎ -nära s2 _g , då: g ( s1 ) ≤rG ( s2 _i minimeringsproblem) _; g ( s ₁ ) ≥ r ^(-G) · g ( s ₂ ) (i maximeringsproblem).
   • En tillräcklig förutsättning för detta är att funktionen g är en polynomfunktion (av b- variabler) med icke-negativa koefficienter.
3. Tekniska villkor :
   • Alla övergångsfunktioner f i F och värdefunktionen g kan utvärderas i polytime.
   • Siffran | F | av övergångsfunktioner är polynom i n och log( X ).
   • ₀ Mängden S av initialtillstånd kan beräknas i tidspolynom i n och log( X ).
   • Låt V _j vara mängden av alla värden som kan förekomma i koordinat j i ett tillstånd. Då ln för varje värde i V _j högst ett polynom P ₁ (n,log(X)).
   • Om dj _, =0 är kardinaliteten för Vj ₎ högst ett polynom P ₂ ( n log( X ).

För varje extremt välvilligt problem kan det dynamiska programmet konverteras till en FPTAS. Definiera:

• $\epsilon$ := det erforderliga approximationsförhållandet.
• ${\displaystyle r:=1+{\frac {\epsilon }{2Gn}}} ,$ där G är konstanten från villkor 2. Observera att ${\frac {1}{\ln {r}}}\leq 1+{\frac {2Gn}{\epsilon }}$ .
• $L:=\left\lceil {\frac {P_{1}(n,\log(X))}{ \ln(r)}}\right\rceil$ , där P ₁ är polynomet från villkor 3 (en övre gräns på ln för varje värde som kan förekomma i en tillståndsvektor). Observera att ${\displaystyle L\leq \left\lceil \left(1+{\frac {2Gn}{\epsilon }}\ right)P_{1}(n,\log {X})\right\rceil } ,$ så det är polynom i storleken på inmatningen och i $1/\epsilon$ . Dessutom, $r^{L}=e^{\ln {r}}\cdot L\geq e^{P_{ 1}(n,\log {x})}$ , så per definition av P ₁ är varje heltal som kan förekomma i en tillståndsvektor inom området [0, r ^L ].
• Dela upp området [0, r ^L ] i L +1 r -intervall: $I_{0}=[0];I_{1}=[1,r);I_{2}=[r,r^{2}); \ldots ;I_{L}=[r^{L-1},r^{L}]$ .
• Dela upp tillståndsutrymmet i r-boxar : varje koordinat k med grad d _k ≥ 1 är uppdelad i L +1-intervallen ovan; varje koordinat med d _k = 0 är uppdelad i P ₂ ( n , log( X )) singeltonintervall - ett intervall för varje möjligt värde på koordinat k (där P ₂ är polynomet från villkor 3 ovan).
  • Observera att alla möjliga tillstånd finns i exakt en r -box; om två tillstånd är i samma r -box, då är de ( d , r )-nära.
• $R:=(L+1+P_{2}(n,\log {X}))^{b}$ .
  • Observera att antalet r -boxar är högst R . Eftersom b är en fast konstant är denna R polynom i storleken på inmatningen och i $1/\epsilon$ .

FPTAS körs på liknande sätt som DP, men i varje steg Tk _trimmar den tillståndsuppsättningen till en mindre uppsättning , som innehåller exakt ett tillstånd i varje r -box. Algoritmen för FPTAS är:

• ₀₀ Låt T := S = mängden initialtillstånd.
• För k = 1 till n gör:
  • Låt U _k := { f ( s , x _k ) | f i F , s i T _{k −1} }
  • Låt T _k := en beskuren kopia av U _k : för varje r -box som innehåller ett eller flera tillstånd av U _k , behåll exakt ett tillstånd i T _k .
• Utgång min/max {g(s) | s i T _n }.

Körtiden för FPTAS är polynom i det totala antalet möjliga tillstånd i varje T _i , vilket är som mest det totala antalet r -boxar, vilket är högst R , vilket är polynom i n , log( X ), och $1/\epsilon$ .

Observera att för varje tillstånd s _u i Uk innehåller _{som är (d,r} dess delmängd Tk ₎ minst ett tillstånd s _t -nära s _u . Varje Uk _. är också en delmängd av Sk _DP i den ursprungliga (otrimmade) Huvudlemmat för att bevisa riktigheten av FPTAS är:

För varje steg k i 0,..., n , för varje tillstånd s _s i Sk _s , finns det ett tillstånd t _i T k _som är ( d , r ^k )-nära s _s .

Beviset är genom induktion på k . För k =0 har vi T _k = S _k ; varje tillstånd är ( d ,1)-nära sig själv. Antag att lemmat gäller för k -1. För varje tillstånd s _s i S _k , låt s- _vara en av dess föregångare i S _k-1 , så att f ( s _{s −} , x ) = s _s . Genom induktionsantagandet finns det ett tillstånd s _t- i T _k-1 , det vill säga ( d , r ^k-1 )-nära s _{s −} . Eftersom närhet bevaras av övergångar (villkor 1 ovan) är f ( s t _{− ,} x ) ( d , r ^k-1 )-nära f ( s _{− ,} x )= s _s . Detta f ( s _{t − ,} x ) är i U _k . Efter trimningen finns det ett tillstånd s _t i T _k som är ( d , r )-nära f(s _t- ,x) . Detta s _t är ( d , r ^k )-nära s _s .

Betrakta nu tillståndet s ^* i S _n , som motsvarar den optimala lösningen (det vill säga g ( s* )=OPT). Enligt lemmat ovan finns det ett tillstånd t * i T _n , som är ( d , r ⁿ )-nära s ^* . Eftersom närhet bevaras av värdefunktionen, g (t*) ≥ r ^(-Gn) · g ( s* ) för ett maximeringsproblem. Enligt definition av r , $r^{-Gn}\geq (1-\epsilon )$ . Så $g(t^{*})\geq (1-\epsilon )\cdot OPT$ . Ett liknande argument fungerar för ett minimeringsproblem.

Exempel

Här är några exempel på extremt välvilliga problem som har en FPTAS enligt ovanstående sats.

₀ 1. Flervägsnummerpartitionering (motsvarande schemaläggning av identiska maskiner ) med målet att minimera den största summan är extremt välvillig. Här har vi a = 1 (ingångarna är heltal) och b = antalet fack (som anses vara fixat). Varje tillstånd är en vektor av b heltal som representerar summorna av b bins. Det finns b funktioner: varje funktion j representerar infogning av nästa ingång i bin j . Funktionen g ( s ) väljer det största elementet av s . S = {(0,...,0)}. Förutsättningarna för extrem välvilja är uppfyllda med gradvektor d =(1,...,1) och G =1. Resultatet sträcker sig till schemaläggning av enhetliga maskiner och schemaläggning av icke-relaterade maskiner närhelst antalet maskiner är fast (detta krävs eftersom R - antalet r -rutor - är exponentiellt i b ). Betecknas Pm|| $\max C_{j}$ eller Qm|| $\max C_{j}$ eller Rm|| $\max C_{j}$ .

• Notera : betrakta specialfallet b =2, där målet är att minimera kvadraten på skillnaden mellan de två delsummorna. Samma DP kan användas, men denna gång med värdefunktion g ( s ) = ( s ₁ - s ₂ ) ² . Nu bryts villkor 2: tillstånden ( s ₁ , s ₁ ) och ( s ₁ , s ₂ ) kan vara ( d,r )-nära, men g ( s ₁ , s ₁ ) = 0 medan g ( s ₁₎ , s ₂ ) > 0. så ovanstående sats kan inte tillämpas. Faktum är att problemet inte har en FPTAS om inte P=NP, eftersom en FPTAS skulle kunna användas för att avgöra i polytime om det optimala värdet är 0.

2. Summan av slutförandetiden för jobb i kuber på ett fast antal identiska eller enhetliga maskiner - det senare betecknat med Qm|| $\sum C_{j}^{3}$ - är ex-välvillig med a =1, b =3, d=(1,1,3). Den kan utökas till vilken som helst fast effekt av färdigställandetiden.

3. Summan av vägd färdigställandetid på ett fast antal identiska eller enhetliga maskiner - den senare betecknad med Qm|| $\sum w_{j}C_{j}$ .

4. Summan av färdigställandetiden på valfritt fast antal identiska eller enhetliga maskiner, med tidsberoende handläggningstider: Qm|time-dep| $\sum C_{j}$ . Detta gäller även för den viktade summan av färdigställandetiden.

5. Viktad tidighet-senlighet med ett vanligt förfallodatum på valfritt fast antal maskiner: m|| $\sum w_{j}|C_{j}|$ .

Enkelt dynamiskt program

Enkla dynamiska program lägger till ovanstående formulering följande komponenter:

• En uppsättning H av filtreringsfunktioner , med samma kardinalitet som F. Varje funktion h _i i H mappar ett par (tillstånd, indata) till ett booleskt värde. Värdet bör vara "true" om och endast om aktivering av övergången _fi på detta par skulle leda till ett giltigt tillstånd.
• En dominansrelation , som är en partiell ordning på tillstånd (inga indifferenser, inte alla par är jämförbara) och en kvasi-dominansrelation som är en total förordning på tillstånd (olikheter tillåtna, alla par är jämförbara).

Den ursprungliga DP ändras enligt följande:

• ₀ Låt S := mängden initialtillstånd.
• För k = 1 till n gör:
  • Låt S _k := { f _j ( s , x _k ) | f _j i F , s i Sk ₋₁ , h _j ( s , x _k )=Sant }, där _h j _är filterfunktionen som motsvarar övergångsfunktionen f _j .
• Utgång min/max {g(s) | s i S _n }.

Ett problem kallas välvilligt om det uppfyller följande villkor (som utökar villkoren 1, 2, 3 ovan):

1. Närhet bevaras av övergångsfunktionerna : För vilken som helst r >1, för vilken övergångsfunktion f i F som helst, för vilken ingångsvektor x som helst, och för alla två tillståndsvektorer s ₁ , s ₂ , gäller följande:
   • om s ₁ är ( d,r )-nära s ₂ ) och s ₁ kvasidominerar s _{2 , då} är f ( s ₁ , x ) ( d,r -nära f ( s ₂ , x _f , och f ( s1 , x ) kvasidominerar f ( s2 _, x ) antingen (a) ) , eller (b) ( s1 , _x ) dominerar f ( s2 _, x ).
   • om s ₁ dominerar s ₂ , då dominerar f ( s ₁ , x ) f ( s ₂ ,x ).
2. Närhet bevaras av värdefunktionen: Det finns ett heltal G ≥ 0 (en funktion av värdefunktionen g och gradvektorn d ), så att för valfri r >1, och för två godtyckliga tillståndsvektorer s ₁ , s ₂ , gäller följande:
   • om _{) (} s1 är ( ,r , och ₍ kvasidominerar s2 , då _· d ⁾ -nära _; s2 _s1 : g s1 ) ≤rG g ( s2 i minimeringsproblem) g ( s ₁ ) ≥ r ^(-G) · g ( s ₂ ) (i maximeringsproblem).
   • om s ₁ dominerar s ₂ , då g ( s ₁ ) ≤ g ( s ₂ ) (i minimeringsproblem); g ( s ₁ ) ≥ g ( s ₂ ) (i maximeringsproblem).
3. Tekniska förhållanden (utöver ovanstående):
   • Kvasidominansrelationen kan bestämmas i polynomtid.
4. Villkor för filterfunktionerna : För valfri r >1, för valfri filterfunktion h i H , för valfri ingångsvektor x , och för valfri två tillståndsvektorer s ₁ , s ₂ , gäller följande:
   • om _, s1 är d -nära s2 _, , x ) . h ( s1 _, x ) ( ( , _r ) _s2 och s1 kvasidominerar s2 _≥h då _
   • om s ₁ dominerar s ₂ , då h ( s ₁ , x ) ≥ h ( s ₂ , x ).

För varje välvilligt problem kan det dynamiska programmet konverteras till en FPTAS på samma sätt som den ovan, med två ändringar (fetstilt):

• ₀₀ Låt T := S = mängden initialtillstånd.
• För k = 1 till n gör:
  • Låt U _k := { f _j ( s , x _k ) | f _j i F , s i T _{k −1} , h _j ( s , x _k )=Sant }, där h _j är filterfunktionen som motsvarar övergångsfunktionen f _j .
  • Låt T _k := en trimmad kopia av U _k : för varje r -box som innehåller ett eller flera tillstånd av U _k , välj ett enda element som kvasidominerar alla andra element i U _k , och infoga det i T _k .
• Utgång min/max {g(s) | s i T _n }.

Exempel

Här är några exempel på välvilliga problem som har en FPTAS enligt ovanstående sats.

1. 0-1 ryggsäcksproblemet är välvilligt. Här har vi en =2: varje ingång är en 2-vektor (vikt, värde). Det finns en DP med b =2: varje tillstånd kodar (aktuell vikt, aktuellt värde). Det finns två övergångsfunktioner: f ₁ motsvarar att lägga till nästa inmatningsobjekt, och f ₂ motsvarar att inte lägga till det. Motsvarande filterfunktioner är: h ₁ verifierar att vikten med nästa inmatade post är som mest ryggsäckens kapacitet; h ₂ returnerar alltid True. Värdefunktionen g ( s ₎ returnerar s2 . Den initiala tillståndsuppsättningen är {(0,0)}. Gradvektorn är (1,1). Dominansrelationen är trivial. Kvasidominansrelationen jämför endast viktkoordinaten: s kvasidominerar t iff s ₁ ≤ t ₁ . Innebörden av detta är att om tillstånd t har en högre vikt än tillstånd s , så tillåts övergångsfunktionerna att inte bevara närheten mellan t och s (det är till exempel möjligt att s har en efterföljare och t inte har har en motsvarande efterträdare). En liknande algoritm presenterades tidigare av Ibarra och Kim. Körtiden för denna FPTAS kan förbättras till $O(n\log {1/\epsilon }+1/\epsilon ^{4})$ operationer på heltal. Exponenten förbättrades senare till 2,5.

• Notera : överväg I det 2-vägda ryggsäcksproblemet , där varje föremål har två vikter och ett värde, och målet är att maximera värdet så att summan av kvadraterna av de totala vikterna som mest är ryggsäckens kapacitet: $\left(\sum _{k\in K}w_{1,k}\right)^{2}+ \left(\summa _{k\in K}w_{2,k}\right)^{2}\leq W$ . Vi skulle kunna lösa det med en liknande DP, där varje tillstånd är (aktuell vikt 1, nuvarande vikt 2, värde). Kvasidominansrelationen bör modifieras till: s kvasidominerar t iff ( s ₁ ² + s ₂ ² ) ≤ ( t ₁ ² + t ₂ ² ). Men det bryter mot villkor 1 ovan: kvasidominans bevaras inte av övergångsfunktioner [till exempel, tillståndet (2,2,..) kvasidominerar (1,3,..); men efter att ha lagt till indata (2,0,..) till båda tillstånden, kommer resultatet (4,2,..) inte att kvasi-dominera (3,3,..)]. Så satsen kan inte användas. Detta problem har faktiskt inte en FPTAS om inte P=NP. Detsamma gäller för det tvådimensionella ryggsäcksproblemet. Detsamma gäller för summaproblemet med flera delmängder : kvasidominansrelationen bör vara: s kvasidominerar t iff max( s _1, s ₂ ) ≤ max( t _{1 ,} t ₂ ), men den bevaras inte av övergångar , med samma exempel som ovan.

2. Minimera det viktade antalet sena jobb, eller maximera det viktade antalet tidiga jobb, på en enda maskin; betecknad 1|| $\sum w_{j}U_{j}$ .

3. Batchschemaläggning för att minimera det viktade antalet sena jobb: 1|batch| $\sum w_{j}U_{j}$ .

4. Omfattning av försämrade jobb på en enda maskin: 1|försämras| $\max C_{j}$ .

5. Totalt sent arbete på en enda maskin: 1|| $\sum V_{j}$ .

6. Totalt viktat sent arbete på en enda maskin: 1|| $\sum w_{j}V_{j}$ .

Icke-exempel

Trots allmänheten i ovanstående resultat finns det fall där det inte kan användas.

1. I det totala fördröjningsproblemet 1|| $\sum T_{j}$ , den dynamiska programmeringsformuleringen av Lawler kräver att alla tillstånd i det gamla tillståndsutrymmet uppdateras några B gånger, där B är av storleksordningen X (den maximala indatastorleken). Detsamma gäller för en DP för ekonomisk partistorlek. är antalet övergångsfunktioner i F B , vilket är exponentiellt i log( X ), så det andra tekniska villkoret bryts. State-trimningstekniken är inte användbar, men en annan teknik - input-rounding - har använts för att designa en FPTAS.

2. I variansminimeringsproblemet 1|| $CTV$ , objektivfunktionen är $g(s)=s_{5}-(s_{4}- s_{3})^{2}/n$ , vilket bryter mot villkor 2, så satsen kan inte användas. Men olika tekniker har använts för att designa en FPTAS.

Några andra problem som har en FPTAS

• Ryggsäcksproblemet , liksom några av dess varianter:
  • 0-1 ryggsäcksproblem.
  • Obegränsat ryggsäcksproblem.
  • Flerdimensionell ryggsäcksproblem med Delta-modulära begränsningar.
  • Multi-objektiv 0-1 ryggsäcksproblem.
  • Parametriskt ryggsäcksproblem.
  • Symmetriskt kvadratiskt ryggsäcksproblem.
• Räkna-delmängd-summa (# DelmängdSum ) - hitta antalet distinkta delmängder med summan av högst C .
• Begränsad kortaste väg : hitta en minimikostnadsväg mellan två noder i en graf, med förbehåll för en fördröjningsbegränsning.
• Kortaste vägarna och icke-linjära mål.
• Räkna kantskydd .
• Sökproblem för vektordelmängder där dimensionen är fixerad.

Se även

• De "välvilliga dynamiska programmen", som tillåter en FPTAS, medger också en evolutionär algoritm.

externa länkar

• Komplexitet Zoo: FPTAS