Approximationsbevarande reduktion

Inom beräkningsbarhetsteori och beräkningskomplexitetsteori , särskilt studiet av approximationsalgoritmer , är en approximationsbevarande reduktion en algoritm för att omvandla ett optimeringsproblem till ett annat problem, så att avståndet mellan lösningar och optimalt bevaras till viss del. Approximationsbevarande reduktioner är en delmängd av mer generella reduktioner i komplexitetsteorin; skillnaden är att approximationsbevarande reduktioner vanligtvis gör uttalanden om approximationsproblem eller optimeringsproblem , i motsats till beslutsproblem .

Intuitivt kan problem A reduceras till problem B via en approximationsbevarande reduktion om man, givet en instans av problem A och en (eventuellt ungefärlig) lösare för problem B, kan omvandla instansen av problem A till en instans av problem B, tillämpa lösaren för problem B, och återskapa en lösning för problem A som också har en viss garanti för approximation.

Definition

Till skillnad från reduktioner på beslutsproblem måste en approximationsbevarande reduktion bevara mer än sanningen i probleminstanserna när man reducerar från ett problem till ett annat. Det måste också upprätthålla en viss garanti för förhållandet mellan kostnaden för lösningen och kostnaden för det optimala i båda problemen. För att formalisera:

Låt $A$ och $B$ vara optimeringsproblem.

Låt $x$ vara en instans av problem $A$ , med optimal lösning ${\text{OPT}}(x)$ . Låt $c_{A}(x,y)$ beteckna kostnaden för en lösning $y$ till en instans $x$ av problem $A$ . Detta är också det mått som används för att avgöra vilken lösning som anses vara optimal.

En approximationsbevarande reduktion är ett par funktioner $(f,g)$ (som ofta måste kunna beräknas i polynomtid), så att:

$f$ mappar en instans $x$ av $A$ till en instans $x'$ av $B$ .
$g$ mappar en lösning $y'$ av $B$ till en lösning $y$ av $A$ .
$g$ bevarar en viss garanti för lösningens prestanda , eller approximationsförhållande $R_{A}(x,y)=\max \left({\frac {c_{A}(x,{\text{OPT}}(x) )}{c_{A}(x,y)}},{\frac {c_{A}(x,y)}{c_{A}(x,{\text{OPT}}(x))}} \right)$ definierad som .

Typer

Det finns många olika typer av approximationsbevarande reduktioner, som alla har olika garanti (den tredje punkten i definitionen ovan). Men till skillnad från andra reduktioner överlappar approximationsbevarande reduktioner ofta i vilka egenskaper de visar på optimeringsproblem (t.ex. komplexitetsklassmedlemskap eller fullständighet, eller inapproximability). De olika typerna av reduktioner används istället som varierande reduktionstekniker, genom att den tillämpliga reduktionen som lättast anpassas till problemet används.

Inte alla typer av approximationsbevarande reduktioner kan användas för att visa medlemskap i alla approximationskomplexitetsklasser, av vilka de mest anmärkningsvärda är PTAS och APX . En minskning nedan bevarar medlemskapet i en komplexitetsklass C om, givet ett problem A som reduceras till problem B via reduktionsschemat, och B är i C, så är A i C också. Vissa minskningar som visas nedan bevarar endast medlemskap i APX eller PTAS, men inte den andra. På grund av detta måste noggrant val göras när man väljer en approximationsbevarande reduktion, särskilt i syfte att bevisa fullständigheten av ett problem inom en komplexitetsklass.

Crescenzi föreslår att de tre mest idealiska reduktionsstilarna, både för enkel användning och beviskraft, är PTAS-reduktion, AP-reduktion och L-reduktion. Reduktionsbeskrivningarna som följer är från Crescenzis kartläggning av approximationsbevarande minskningar.

Strikt minskning

Strikt reduktion är den enklaste typen av approximationsbevarande reduktion. I en strikt reduktion måste approximationsförhållandet för en lösning y' till en instans x' av ett problem B vara högst lika bra som approximationsförhållandet för motsvarande lösning y till instans x av problem A. Med andra ord:

{\displaystyle R_{A}(x,y)\leq R_{B}(x',y')

för

x'=f(x),y=g(y')

.

Strikt reduktion är det enklaste: om det finns en strikt reduktion från problem A till problem B, så kan problem A alltid approximeras till minst lika bra förhållande som problem B. Strikt reduktion bevarar medlemskapet i både PTAS och APX.

Det finns ett liknande koncept för en S-reduktion, för vilken $c_{A}(x,y)=c_{B}(x' ,y')$ , och optima för de två motsvarande instanserna måste också ha samma kostnad. S-reduktion är ett mycket speciellt fall av strikt reduktion, och är ännu mer begränsande. I själva verket måste de två problemen A och B vara i nästan perfekt överensstämmelse med varandra. Förekomsten av en S-reduktion innebär inte bara förekomsten av en strikt minskning utan varje annan minskning som anges här.

L-reduktion

L-reduktioner bevarar medlemskapet i PTAS såväl som APX (men endast för minimeringsproblem i fallet med det senare) . Som ett resultat kan de inte användas i allmänhet för att bevisa fullständighetsresultat om APX, Log-APX eller Poly-APX, men ändå värderas de för sin naturliga formulering och användarvänlighet i korrektur.

PTAS-reduktion

PTAS-reduktion är ett annat vanligt förekommande reduktionsschema. Även om det bevarar medlemskapet i PTAS, gör det inte det för APX. Ändå definieras APX-fullständighet i termer av PTAS-reduktioner.

PTAS-reduktioner är en generalisering av P-reduktioner, som visas nedan, med den enda skillnaden att funktionen $g$ tillåts bero på approximationsförhållandet $r$ .

A-reduktion och P-reduktion

A-reduktion och P-reduktion är liknande reduktionsprogram som kan användas för att visa medlemskap i APX respektive PTAS. Båda introducerar en ny funktion $c$ , definierad på tal större än 1, som måste vara beräkningsbar.

I en A-reduktion har vi det

{\displaystyle R_{B}(x',y')\leq r\rightarrow R_{A}(x

.

I en P-reduktion har vi det

{\displaystyle R_{B}(x',y')\leq c(r)\högerpil R_{A

.

Förekomsten av en P-reduktion innebär att det finns en PTAS-reduktion.

E-reduktion

E-reduktion, som är en generalisering av strikt reduktion men innebär både A-reduktion och P-reduktion, är ett exempel på en mindre restriktiv reduktionsstil som bevarar medlemskapet inte bara i PTAS och APX, utan även de större klasserna Log- APX och Poly-APX . E-reduktion introducerar två nya parametrar, ett polynom $p$ och en konstant $\beta$ . Dess definition är följande.

I en E-reduktion har vi det för något polynom $p$ och konstant $\beta$ ,

${\displaystyle c_{B}({\text{OPT}}_{B}(x')) \leq p(|x|)c_{A}({\text{OPT}}_{A}(x))} ,$ där $|x|$ anger storleken på probleminstansens beskrivning.
För alla lösningar $y'$ till $B ,$ $R_{A}(x ,y)\leq 1+\beta \cdot (R_{B}(x',y')-1)$ vi .

För att få en A-reduktion från en E-reduktion, låt ${\displaystyle c(r)=1+\beta \cdot (r-1)} ,$ och till få en P-reduktion från en E-reduktion, låt $c(r)=1+(r-1)/\beta$ .

AP-reduktion

AP-reduktioner används för att definiera fullständighet i klasserna Log-APX och Poly-APX . De är ett specialfall av PTAS-reduktion, som uppfyller följande begränsningar.

I en AP-reduktion har vi det för någon konstant $\alpha$ ,

leq r\högerpil R_{ A}(x,y)\leq 1+\alpha \cdot (r-1)}

med den ytterligare generaliseringen att funktionen $g$ tillåts bero på approximationsförhållandet $r$ , som i PTAS-reduktion.

AP-reduktion är också en generalisering av E-reduktion. En ytterligare begränsning måste faktiskt införas för AP-reduktion för att bevara Log-APX- och Poly-APX-medlemskap, som E-reduction gör: för fast problemstorlek måste beräkningstiden för f, g vara icke-ökande $som$ approximationsförhållande ökar.

Gapminskning

En gapreduktion är en typ av minskning som, även om den är användbar för att bevisa vissa inapproximability-resultat, inte liknar de andra minskningarna som visas här. Gap reductions hanterar optimeringsproblem inom en beslutsproblembehållare, genererade genom att ändra problemmålet till att skilja mellan den optimala lösningen och lösningarna, någon multiplikativ faktor som är sämre än den optimala.

Se även