Parameteriserad approximationsalgoritm

En parametriserad approximationsalgoritm är en typ av algoritm som syftar till att hitta ungefärliga lösningar på NP-hårda optimeringsproblem i polynomtid i indatastorleken och en funktion av en specifik parameter. Dessa algoritmer är designade för att kombinera de bästa aspekterna av både traditionella approximationsalgoritmer och följsamhet med fasta parametrar.

I traditionella approximationsalgoritmer är målet att hitta lösningar som är högst en viss faktor $\alpha$ borta från den optimala lösningen, känd som en $\alpha$ -approximation, i polynomtid. Å andra sidan är parameteriserade algoritmer utformade för att hitta exakta lösningar på problem, men med begränsningen att algoritmens körtid är polynom i inmatningsstorleken och en funktion av en specifik parameter k {\displaystyle $}$ . Parametern beskriver en viss egenskap hos ingången och är liten i typiska applikationer. Problemet sägs vara fixparameter tractable (FPT) om det finns en algoritm som kan hitta den optimala lösningen i $f(k)n^{O(1)}$ tid, där $f(k)$ är en funktion oberoende av ingångsstorleken $n$ .

En parametriserad approximationsalgoritm syftar till att hitta en balans mellan dessa två tillvägagångssätt genom att hitta ungefärliga lösningar i FPT-tid: algoritmen beräknar en $\alpha$ -approximation i $f(k )n^{O(1)}$ tid, där $f(k)$ är en funktion oberoende av ingångsstorleken $n$ . Detta tillvägagångssätt syftar till att övervinna begränsningarna för båda traditionella tillvägagångssätten genom att ha starkare garantier för lösningens kvalitet jämfört med traditionella approximationer samtidigt som de fortfarande har effektiva körtider som i FPT-algoritmer. En översikt över forskningsområdet som studerar parametriserade approximationsalgoritmer finns i Marx undersökning och den nyare undersökningen av Feldmann et al.

Erhållbara approximationsförhållanden

Den fulla potentialen hos parametriserade approximationsalgoritmer utnyttjas när ett givet optimeringsproblem visas för att tillåta en $\alpha$ -approximationsalgoritm som körs i $f(k)n^{ O(1)}$ tid, medan problemet däremot inte har en polynom-tid $\alpha$ -approximationsalgoritm (under vissa komplexitetsantaganden , t.ex. $\neq NP} )$ P , inte heller en FPT-algoritm för den givna parametern $k$ (dvs den är åtminstone W[1]-hard ) .

Till exempel, vissa problem som är APX-hårda och W[1]-hårda medger ett parameteriserat approximationsschema (PAS) , dvs. för alla $\varepsilon >0$ a $( 1+\varepsilon )$ -approximation kan beräknas i $f(k,\varepsilon )n^{g(\varepsilon )}$ tid för vissa funktioner ${\ displaystyle f}$ och $g$ . Detta kringgår sedan de nedre gränserna när det gäller polynom-tidsapproximation och följbarhet med fasta parametrar. En PAS liknar till sin anda ett polynom-tidsapproximationsschema (PTAS) men utnyttjar dessutom en given parameter $k$ . Eftersom graden av polynomet i körtiden för ett PAS beror på en funktion ${\displaystyle g(\varepsilon )} , antas$ värdet på $\varepsilon$ vara godtyckligt men konstant för att PAS för att köras i FPT-tid. Om detta antagande inte är tillfredsställande, behandlas ${\displaystyle \varepsilon } som en parameter också för att erhålla ett$ effektivt parameteriserat approximationsschema (EPAS) , som för alla $\varepsilon >0$ beräknar a $(1+\varepsilon )$ -approximation i $f(k,\varepsilon )n^{O(1)}$ tid för någon funktion ${ \displaystyle f}$ . Detta liknar till sin anda ett effektivt polynom-tidsapproximationsschema (EPTAS).

k-Cut

K -cut- problemet har ingen polynom-tid $(2-\varepsilon )$ -approximationsalgoritm för någon $\varepsilon >0$ , med antagande av $P \neq NP$ och Small Set Expansion Hypothesis. Den är också W[1]-hård parametrerad av antalet $k$ av nödvändiga komponenter. Det finns emellertid en EPAS som beräknar en $(1+\varepsilon )$ -approximation i $(k/\varepsilon )^ {O(k)}n^{O(1)}$ tid.

Steinerträd

Steiner Tree-problemet är FPT-parameteriserat av antalet terminaler. Men för den "dubbla" parametern som består av antalet $k$ av icke-terminaler som ingår i den optimala lösningen, är problemet W[2]-hårt (på grund av en folkloristisk minskning från problemet med Dominating Set ). Steiner Tree är också känt för att vara APX-hårt . Det finns dock en EPAS som beräknar en $(1+\varepsilon )$ -approximation i $2^{O(k^ {2}/\varepsilon ^{4})}n^{O(1)}$ tid.

Starkt ansluten Steiner Subgraph

$) {\displaystyle O( \log ^{2-\varepsilon }n)}$ ]-hårt parametriserat av antalet $k$ av terminaler, och inte heller medger ett -approximation i polynomtid (under standardkomplexitetsantaganden ) . En 2-approximation kan dock beräknas på $3^{k}n^{O(1)}$ tid. Dessutom är detta bäst möjligt, eftersom ingen $(2-\varepsilon )$ -approximation kan beräknas i $f(k)n^{O (1)}$ tid för valfri funktion $f$ , under Gap- ETH .

k-median och k-medel

För de välstuderade metriska klustringsproblemen för k-Median och k-Means parametriserade av antalet $k$ av centra, är det känt att ingen $(1+2) /e-\varepsilon )$ -approximation för k-Median och no $(1+8/e-\varepsilon )$ -approximation för k-Means kan beräknas i $f(k)n^{O(1)}$ tid för valfri funktion $f$ , under Gap- ETH . Matchande parameteriserade approximationsalgoritmer finns, men det är inte känt om matchande approximationer kan beräknas i polynomtid.

Klustring övervägs ofta i inställningar med lågdimensionella data, och därför är en praktiskt relevant parameterisering av dimensionen för det underliggande måttet . I det euklidiska utrymmet tillåter problemen med k-Median och k-Means en EPAS parametriserad av dimensionen ${\displaystyle d},$ och även en EPAS parametriserad av $k$ . Den förra generaliserades till en EPAS för parametrisering av dubbleringsdimensionen . För den löst relaterade dimensionsparametern för motorvägar är endast ett approximationsschema med XP- körtid känt till dags dato.

k-Center

För det metriska k-Center-problemet kan en 2-approximation beräknas i polynomtid. Men när man parametriserar med antingen numret $k$ för centra, dubbleringsdimensionen (i själva verket dimensionen för en Manhattan-metrik ), eller motorvägsdimensionen, blir ingen parametriserad $(2-\ varepsilon )$ -approximationsalgoritm finns, under standardkomplexitetsantaganden . Dessutom är k-Center-problemet W[1]-svårt även på plana grafer när det samtidigt parametreras med antalet $k$ av centra, dubbleringsdimensionen , motorvägsdimensionen och vägbredden . Men när ${\displaystyle k} kombineras$ med dubbleringsdimensionen existerar en EPAS, och detsamma gäller när ${\displaystyle k} kombineras$ med motorvägsdimensionen. För den mer generella versionen med vertexkapacitet finns en EPAS för parametrisering med k och dubbleringsdimensionen, men inte när k och motorvägsdimensionen används som parameter. När det gäller sökvägsbredden tillåter k-Center en EPAS även för den mer allmänna trädbreddsparametern och även för klickbredd .

Tätaste subgraf

En optimeringsvariant av k-Clique-problemet är Densest k-Subgraph-problemet (som är ett 2-ary Constraint Satisfaction-problem ), där uppgiften är att hitta en subgraf på $k$ hörn med maximalt antal kanter. Det är inte svårt att få en $(k-1)$ -approximation genom att bara välja en matchning av storlek $k/2$ i den givna inmatningsgrafen, eftersom det maximala antalet av kanter på $k$ hörn är alltid som mest ${k \choose 2}=k(k-1)/2$ . Detta är också asymptotiskt optimalt, eftersom under Gap- ETH no $k^{1-o(1)}$ -approximation kan beräknas i FPT-tid parametriserad av $k$ .

Dominerande uppsättning

För problemet med dominerande uppsättning är det W[1]-svårt att beräkna någon $g(k)$ -approximation i $f(k)n^{ O(1)}$ tid för alla funktioner $g$ och $f$ .

Ungefärlig kärnbildning

Kernelisering är en teknik som används för att förbehandla en instans av ett NP-hårt problem för att ta bort "enkla delar" och avslöja den NP-hårda kärnan i instansen. En kerneliseringsalgoritm tar en instans $I$ och en parameter $k$ , och returnerar en ny instans $I'$ med parametern $k'$ så att storleken på $I'$ och $k'$ är begränsad som en funktion av indataparametern $k$ , och algoritmen körs i polynomtid. En $\alpha$ -approximate kerneliseringsalgoritm är en variant av denna teknik som används i parametriserade approximationsalgoritmer. Den returnerar en kärna $I'$ så att varje $\beta$ -approximation i $I'$ kan omvandlas till en $\alpha \beta$ -approximation till ingångsinstansen $I$ i polynomtid. Detta begrepp introducerades av Lokshtanov et al., men det finns andra relaterade begrepp i litteraturen såsom Turing-kärnor och $\alpha$ -fidelity-kärnisering.

När det gäller vanliga (icke-approximativa) kärnor, tillåter ett problem en α-approximativ kärnbildningsalgoritm om och endast om den har en parametriserad α-approximationsalgoritm. Beviset för detta faktum är mycket likt det för vanliga kärnor . Den garanterade ungefärliga kärnan kan dock vara av exponentiell storlek (eller värre) i indataparametern. Därför blir det intressant att hitta problem som tillåter ungefärliga kärnor av polynomstorlek. Dessutom är ett approximativt kärnbildningsschema (PSAKS) i polynomstorlek en $\alpha$ -approximate kerneliseringsalgoritm som beräknar en kärna i polynomstorlek och för vilken $\alpha$ kan sättas till ${ \displaystyle 1+\varepsilon }$ för alla $\varepsilon >0$ .

Till exempel, medan Connected Vertex Cover-problemet är FPT-parametriserat av lösningsstorleken, tillåter det inte en kärna (vanlig) polynomstorlek (såvida inte $\displaystyle NP\subseteq coNP/ poly}$ ), men en PSAKS finns. På liknande sätt är Steiner Tree-problemet FPT parametriserat av antalet terminaler, tillåter inte en kärna av polynomstorlek (såvida inte ${\displaystyle NP\subseteq coNP/poly} )$ , men en PSAKS finns. När man parametriserar Steiner Tree med antalet icke-terminaler i den optimala lösningen, är problemet W[2]-hårt (och medger alltså ingen exakt kärna alls, såvida inte FPT=W[2]), men medger fortfarande en PSAKS.