Karmarkar-Karp bin packningsalgoritmer

Karmarkar -Karp (KK) binpackningsalgoritmer är flera relaterade approximationsalgoritmer för binpackningsproblemet . Fackpackningsproblemet är ett problem med att packa föremål av olika storlekar i kärl med identisk kapacitet, så att det totala antalet kärl blir så litet som möjligt. Att hitta den optimala lösningen är beräkningsmässigt svårt . Karmarkar och Karp tog fram en algoritm som körs i polynomtid och $\mathrm {OPT} +{\mathcal {O}$ som mest fack, där OPT är antalet fack i den optimala lösningen. De utarbetade också flera andra algoritmer med något annorlunda approximationsgarantier och körtidsgränser.

KK-algoritmerna ansågs vara ett genombrott i studien av binpackning: de tidigare kända algoritmerna fann multiplikativ approximation, där antalet fack var som mest $r\cdot \mathrm {OPT} + s$ för vissa konstanter ${\displaystyle r>1,s>0} ,$ eller som mest $(1+\varepsilon )\mathrm {OPT} +1$ . KK-algoritmerna var de första som uppnådde en additiv approximation.

Inmatning

Ingången till ett bin-packningsproblem är en uppsättning artiklar av olika storlekar, a ₁ ,... a _n . Följande notation används:

• n - antalet artiklar.
• m - antalet olika objektstorlekar. För varje i på 1,..., m :
  • s _i är den i -te storleken;
  • n _i är antalet föremål i storleken s _i .
• B - behållarens storlek.

Givet ett fall I betecknar vi:

• OPT(I) = den optimala lösningen av instans I .
• FOPT( I ) = ( a ₁ +...+ a _n )/ B = det teoretiskt optimala antalet fack, när alla fack är helt fyllda med artiklar eller artikelfraktioner.

Uppenbarligen är FOPT( I ) ≤ OPT(I).

System på hög nivå

KK-algoritmerna löser i huvudsak det linjära konfigurationsprogrammet :

${\text{minimize}}~~\mathbf {1} \cdot \mathbf {x} ~~~{\text{st}}~~A\ mathbf {x} \geq \mathbf {n} ~~~{\text{and}}~~\mathbf {x} \geq 0~~~{\text{and}}~~\mathbf {x} ~{ \text{är ett heltal}}~$ .

Här är A en matris med m rader. Varje kolumn av A representerar en genomförbar konfiguration - en multiuppsättning av objektstorlekar, så att summan av alla dessa storlekar är som mest B . Uppsättningen av konfigurationer är C . x är en vektor med storlek C. Varje element xc _. av x representerar antalet gånger som konfiguration c används

• Exempel : anta att artikelstorlekarna är 3,3,3,3,3,4,4,4,4,4 och B =12. Sedan finns det C =10 möjliga konfigurationer: 3333; 333; 33, 334; 3, 34, 344; 4, 44, 444. Matrisen A har två rader: [4,3,2,2,1,1,1,0,0,0] för s=3 och [0,0,0,1,0, 1,2,1,2,3] för s=4. Vektorn n är [5,5] eftersom det finns 5 objekt av varje storlek. En möjlig optimal lösning är x =[1,0,0,0,0,0,1,0,0,1], vilket motsvarar att använda tre fack med konfigurationerna 3333, 344, 444.

Det finns två huvudsakliga svårigheter att lösa detta problem. För det första är det ett linjärt heltalsprogram , vilket är beräkningsmässigt svårt att lösa. För det andra är antalet variabler C - antalet konfigurationer, vilket kan vara enormt. KK-algoritmerna hanterar dessa svårigheter med hjälp av flera tekniker, av vilka några redan introducerades av de-la-Vega och Lueker. Här är en beskrivning på hög nivå av algoritmen (där $I$ är den ursprungliga instansen):

• 1-a. Låt $J$ vara en instans konstruerad från $I$ genom att ta bort små objekt.
  • 2-a. Låt $K$ vara en instans konstruerad från $J$ genom att gruppera objekt och avrunda storleken på objekt i varje grupp till det högsta objektet i gruppen.
    • 3-a. Konstruera det linjära konfigurationsprogrammet för $K$ , utan integralitetsbegränsningarna.
      • 4. Beräkna en (fraktionell) lösning x för det avslappnade linjära programmet.
    • 3-b. Avrunda x till en integrallösning för $K$ .
  • 2-b. "Avgruppera" objekten för att få en lösning för $J$ .
• 1-b. Lägg till de små föremålen för att få en lösning för $I$ .

Nedan beskriver vi vart och ett av dessa steg i tur och ordning.

Steg 1. Ta bort och lägga till små föremål

Motivet för att ta bort små föremål är att när alla föremål är stora måste antalet föremål i varje papperskorg vara litet, så antalet möjliga konfigurationer är (relativt) litet. Vi väljer någon konstant $g\in (0,1)$ , och tar bort från den ursprungliga instansen $I$ alla objekt mindre än $g\cdot B$ . Låt $J$ vara den resulterande instansen. Observera att i $J$ kan varje fack innehålla högst $1/g$ objekt. Vi packar $J$ och får en packning med några $b_{J}$ fack.

Nu lägger vi till de små föremålen i de befintliga papperskorgen i en godtycklig ordning, så länge det finns plats. När det inte finns mer plats i de befintliga kärlen, öppnar vi en ny behållare (som i nästa-fit kärlpackning) . Låt $b_{I}$ vara antalet papperskorgar i den slutliga förpackningen. Sedan:

$b_{I}\leq \max(b_{J},(1+2g)\cdot OPT( I)+1)$ .

Bevis . Om inga nya fack öppnas förblir antalet fack $b_{J}$ . Om en ny papperskorg öppnas innehåller alla fack utom kanske den sista en total storlek på minst $Bg\cdot B$ , så den totala instansstorleken är minst $(1-g)\cdot B\cdot (b_{I}-1)$ . Därför ${\displaystyle FOPT\geq (1-g)\cdot (b_{I}-1)} ,$ så den optimala lösningen behöver minst $(1-g)\cdot (b_{I}-1)$ fack. Så $displaystyle b_{I$ . I synnerhet, genom att ta g =1/ n , får vi:

$\displaystyle b_{I}\leq \max($ ,

eftersom $OPT(I)\leq n$ . Därför är det vanligt att anta att alla objekt är större än 1/ n .

Steg 2. Gruppera och avgruppera objekt

Motivet för att gruppera artiklar är att minska antalet olika objektstorlekar, att minska antalet begränsningar i konfigurationen LP. Den allmänna grupperingsprocessen är:

• Beställ föremålen efter fallande storlek.
• Dela upp objekten i grupper.
• För varje grupp, ändra storleken på alla objekt i gruppen till den största storleken i gruppen.

Det finns flera olika grupperingsmetoder.

Linjär gruppering

Låt $k>1$ vara en heltalsparameter. Lägg de största $k$ objekten i grupp 1; de näst största $k$ objekten i grupp 2; och så vidare (den sista gruppen kan ha färre än $k$ objekt). Låt $J$ vara den ursprungliga instansen. Låt $K'$ vara den första gruppen (gruppen av de $k$ största objekten), och $K$ den grupperade instansen utan den första gruppen. Sedan:

• I $K'$ har alla objekt samma storlek. I $K$ är antalet olika storlekar $m(K)\leq n/k+1$ .
• $OPT(K)\leq OPT(J)$ eftersom grupp 1 i $J$ dominerar grupp 2 i $K$ (alla k objekt i grupp 1 är större än k objekt i grupp 2); på samma sätt dominerar grupp 2 i ${\displaystyle J} grupp 3 i$$K$ osv.
• $OPT(K')\leq k$ - eftersom det är möjligt att packa varje artikel i $K'$ i en enda papperskorg.

Därför $J)$ . Givet en lösning till $K$ med $b_{K}$ bins, kan vi faktiskt få en lösning till $J$ med högst $b_{K }+k$ fack.

Geometrisk gruppering

Låt $k>1$ vara en heltalsparameter. Geometrisk gruppering sker i två steg:

• Partitionera instansen $J$ i flera instanser $J_{0},J_{1},\ldots$ så att i varje instans $J_{r}$ , alla storlekar är i intervallet $[B/2^{r+1},B/2^{r})$ . Observera att om alla objekt i $J$ har storleken minst $g\cdot B$ , så är antalet instanser som mest $\log _{2}(1/g)$ .
• För varje instans $J_{r}$ utför du linjär avrundning med parametern $k\cdot 2^{r}$ . Låt $K_{r},K'_{r}$ vara de resulterande instanserna. Låt $K:=\cup _{r}K_{r}$ och $K':=\cup _{r}K' _{r}$ .

Sedan avgränsas antalet olika storlekar enligt följande:

• För alla r , $m(K'_{r})=1$ och ${\ displaystil m(K_{r})\leq n(J_{r})/(k\cdot 2^{r})+1}$ . Eftersom alla objekt i $J_{r}$ är större än $B/2^{r+1}$ , har vi ${\displaystyle n(J_{r})\leq 2^{r+1}\cdot FOPT(J_{r})} ,$ så $m(K_{r})\leq 2FOPT(J_{r})/k+1$ . Att summera över alla r ger $m(K)\leq 2FOPT(J)/k+\log _{2} (1/g)$ .

Antalet fack är avgränsat enligt följande:

• För alla r , $OPT(K'_{r})\leq k$ - eftersom $K'_{r}$ har $k\cdot 2^{r}$ objekt, och alla är mindre än $B/2^{r}$ , så de kan packas i högst $k$ papperskorgar.
• Därför, $OPT(K')\leq k\cdot \log _{2}(1/g)$ .
• Därför $\displaystyle OPT(J)$ .

Alternativ geometrisk gruppering

Låt $k>1$ vara en heltalsparameter. Beställ föremålen efter fallande storlek. Dela upp dem i grupper så att den totala storleken i varje grupp är minst $k\cdot B$ . Eftersom storleken på varje objekt är mindre än B , är antalet objekt i varje grupp minst $k+1$ . Antalet föremål i varje grupp ökar svagt. Om alla objekt är större än $g\cdot B$ , då är antalet objekt i varje grupp högst $k/g$ . I varje grupp avrundas endast de större föremålen uppåt. Detta kan göras så att:

• $m(K)\leq FOPT(J)/k+\ln(1/g)$ .
• $\displaystyle OPT(J)\leq OPT(K)+2k\cdot (2+\ln (1/g))}$ .

Steg 3. Konstruera LP och runda lösningen

Vi betraktar det linjära konfigurationsprogrammet utan integralitetsbegränsningarna:

${\text{minimera}}~~\mathbf {1} \cdot \mathbf {x} ~~~{\text{st}}~~A\mathbf {x} \ geq \mathbf {n} ~~~{\text{och}}~~\mathbf {x} \geq 0$ .

Här får vi använda ett bråktal av varje konfiguration.

• Exempel : anta att det finns 31 artiklar i storlek 3 och 7 artiklar i storlek 4, och lådans storlek är 10. Konfigurationerna är: 4, 44, 34, 334, 3, 33, 333. Begränsningarna är [0,0 ,1,2,1,2,3]* x =31 och [1,2,1,1,0,0,0]* x =7. En optimal lösning på fraktionerad LP är [0,0,0,7,0,0,17/3] Det vill säga: det finns 7 fack med konfiguration 334 och 17/3 fack av konfiguration 333. Observera att endast två olika konfigurationer är behövda.

Ange den optimala lösningen för det linjära programmet med LOPT. Följande relationer är uppenbara:

• FOPT(I) ≤ LOPT(I), eftersom FOPT(I) är antalet (möjligen bråkdelar) av fack när alla fack är helt fyllda med artiklar eller bråkdelar av objekt. Det är uppenbart att ingen lösning kan vara mer effektiv.
• LOPT(I) ≤ OPT(I), eftersom LOPT(I) är en lösning på ett minimeringsproblem med färre begränsningar.
• OPT(I) < 2*FOPT(I), eftersom i varje packning med minst 2*FOPT(I)-fack är summan av de två minst fulla fack högst B , så de kan kombineras till en enda fack .

En lösning till fraktionell LP kan avrundas till en integrerad lösning enligt följande.

Antag att vi har en lösning x till bråktalet LP. Vi avrundar x till en lösning för den integrerade ILP enligt följande.

• Låt x vara en optimal grundläggande genomförbar lösning av fraktionell LP. Antag att det är $\sum _{c\in C}x_{c}=b_{L}$ bins (observera att $b_{L}$ kan vara ett bråktal). Eftersom bråk-LP har m begränsningar (en för varje distinkt storlek), har x högst m icke-nollvariabler, det vill säga högst m olika konfigurationer används. Vi konstruerar av x en integrerad packning som består av en huvuddel och en restdel .
• Huvuddelen innehåller golv( x _c )-fack för varje konfiguration c för vilka x _c > 0.
• För restdelen (betecknad med R ) konstruerar vi två kandidatpackningar:
  • Ett enda fack för varje konfiguration c för vilket x _c > 0; allt som allt behövs m soptunnor.
  • En girig packning, med färre än 2*FOPT( R )-fack (eftersom om det finns minst 2*FOPT( R )-fack, kan de två minsta kombineras).
• Den minsta av dessa packningar kräver min( m , 2*FOPT( R )) ≤ medel( m , 2*FOPT( R )) = FOPT(R) + m /2.
• Om man lägger till detta de avrundade fackarna för huvuddelen ger som mest $b_{L}+m/2$ fack.
• Exekveringstiden för denna omvandlingsalgoritm är O( n log n ).

Detta innebär också att $I)+m/2}$ .

Steg 4. Lösning av fraktionerad LP

Den största utmaningen med att lösa bråk-LP är att den kan ha ett stort antal variabler - en variabel för varje möjlig konfiguration.

Den dubbla LP:n

Det dubbla linjära programmet för fraktionell LP är:

${\text{maximize}}~~\mathbf {n} \cdot \mathbf {y} ~~~{\text{st}}~~A^{T}\ mathbf {y} \leq \mathbf {1} ~~~{\text{and}}~~\mathbf {y} \geq 0$ .

Den har m variabler $y_{1},\ldots ,y_{m}$ och C- begränsningar - en begränsning för varje konfiguration. Den har följande ekonomiska tolkning. För varje storlek s bör vi bestämma ett icke-negativt pris $y_{i}$ . Vår vinst är det totala priset på alla varor. Vi vill maximera vinsten n y med förbehåll för begränsningarna att det totala priset för artiklar i varje konfiguration är högst 1. Denna LP har nu bara m variabler, men ett stort antal begränsningar. Att ens lista alla begränsningar är omöjligt.

Lyckligtvis är det möjligt att lösa problemet upp till vilken precision som helst utan att lista alla begränsningar, genom att använda en variant av ellipsoidmetoden . Denna variant får som indata ett separationsorakel : en funktion som, givet en vektor y ≥ 0, returnerar ett av följande två alternativ:

• Påstå att y är genomförbart, det vill säga $A^{T}\mathbf {y} \leq \mathbf {1}$ ; eller -
• Påstå att y är omöjligt, och returnera en specifik begränsning som överträtts, det vill säga en vektor a sådan att $\mathbf {a} \cdot \mathbf {y} >1$ .

Ellipsoidmetoden börjar med en stor ellipsoid, som innehåller hela den möjliga domänen $A^{T}\mathbf {y} \leq \mathbf {1}$ . Vid varje steg t tar den mitten $\mathbf {y} _{t}$ av den aktuella ellipsoiden och skickar den till separationsoraklet:

• Om oraklet säger att $\mathbf {y} _{t}$ är genomförbart, så gör vi ett "optimalitetssnitt": vi skär från ellipsoiden alla punkter y för vilka $\mathbf {n} \cdot \mathbf {y} <\mathbf {n} \cdot \mathbf {y} _{t}$ . Dessa punkter är definitivt inte optimala.
• Om oraklet säger att $\mathbf {y} _{t}$ är omöjligt och bryter mot begränsningen a , så gör vi ett "feasibility cut": vi skär från ellipsoiden alla punkter y för vilka $\mathbf {a} \cdot \mathbf {y} >1$ . Dessa punkter är definitivt inte genomförbara.

Efter att ha gjort ett snitt konstruerar vi en ny, mindre ellipsoid. Det kan visas att denna process konvergerar till en ungefärlig lösning, i tidspolynom med erforderlig noggrannhet.

Ett separationsorakel för den dubbla LP:n

Vi får några m icke-negativa tal $y_{1},\ldots ,y_{m}$ . Vi måste välja mellan följande två alternativ:

• För varje möjlig konfiguration är summan av $y_{i}$ som motsvarar denna konfiguration högst 1; detta betyder att y är genomförbart.
• Det finns en möjlig konfiguration för vilken summan av $y_{i}$ är större än 1; detta betyder att y är omöjligt. I det här fallet måste vi också returnera konfigurationen.

Detta problem kan lösas genom att lösa ett ryggsäcksproblem , där artikelvärdena är $y_{1},\ldots ,y_{m}$ , föremålens vikter är $s_{1},\ldots ,s_{m}$ och viktkapaciteten är B (behållarens storlek).

• Om det totala värdet av den optimala ryggsäckslösningen är högst 1, så säger vi att y är genomförbart.
• Om det totala värdet av den optimala ryggsäckslösningen är större än 1, så säger vi att y är omöjligt, och objekten i den optimala ryggsäckslösningen motsvarar en konfiguration som bryter mot en begränsning (eftersom $\mathbf {a} \cdot \mathbf {y} >1$ för vektorn a som motsvarar denna konfiguration).

Ryggsäcksproblemet kan lösas genom dynamisk programmering i pseudopolynomtid: $O(m\cdot V)$ , där m är antalet ingångar och V är antalet olika möjliga värden. För att få en polynom-tidsalgoritm kan vi lösa ryggsäcksproblemet ungefär genom att använda ingångsavrundning. Anta att vi vill ha en lösning med tolerans $\delta$ . Vi kan avrunda var och en av $y_{1},\ldots ,y_{m}$ nedåt till närmaste multipel av $\delta$ / n . Sedan är antalet möjliga värden mellan 0 och 1 n / $\delta$ , och körtiden är $O(mn/\delta )$ . Lösningen är åtminstone den optimala lösningen minus $\delta$ / n .

Ellipsoid metod med ett ungefärligt separationsorakel

Ellipsoidmetoden bör anpassas för att använda ett ungefärligt separationsorakel. Givet den nuvarande ellipsoidens mittpunkt $\mathbf {y} _{t}$ :

• Om det ungefärliga oraklet returnerar en lösning med ett värde större än 1, så är $\mathbf {y} _{t}$ definitivt omöjligt, och lösningen motsvarar en konfiguration som bryter mot en begränsning a . Vi gör en "feasibility cut" i $\mathbf {y} _{t}$ , skär ellipsoiden alla punkter y för vilka $\mathbf {a} \cdot \mathbf { y} >1$ .
• Om det ungefärliga oraklet returnerar en lösning med ett värde som högst 1, så kan ${\displaystyle \mathbf {y} _{t}} vara genomförbart eller inte, men$$\mathbf {y} _{t }$ avrundat nedåt (beteckna det med $\mathbf {z} _{t}$ ) är genomförbart. Per definition av avrundningen vet vi att $\mathbf {n} \cdot \mathbf {z} _{t}\geq \mathbf {n} \cdot \mathbf {y} _{t}-\mathbf {n} \cdot \mathbf {1} \cdot (\delta /n)=\mathbf {n} \ cdot \mathbf {y} _{t}-\delta$ . Vi gör fortfarande ett "optimality cut" i $\mathbf {y} _{t}$ : vi skär från ellipsoiden alla punkter y för vilka $\mathbf {n } \cdot \mathbf {y} <\mathbf {n} \cdot \mathbf {y} _{t}$ . Observera att $\mathbf {y} _{t}$ kan vara omöjligt, så dess värde kan vara större än OPT. Därför kan vi ta bort några punkter vars mål är optimalt. De borttagna punkterna uppfyller dock ${\displaystyle \mathbf {n} \cdot \mathbf {y} <\mathbf {n} \cdot \mathbf {z} _{ t}+\delta \leq {\text{OPT}}+\delta} [$ ; ingen punkt tas bort om dess värde överstiger värdet vid $\mathbf {z} _{t}$ med mer än $\delta$ .

Att använda det ungefärliga separationsoraklet ger en möjlig lösning y* till den dubbla LP, med $\mathbf {n} \cdot \mathbf {y^{*}} \geq LOPT -\delta$ , efter högst $Q$ iterationer, där $Q=4m^{2}\ln(mn/g\delta )$ . Den totala körtiden för ellipsoidmetoden med det ungefärliga separationsoraklet är $O(Qmn/\delta )$ .

Eliminera begränsningar

Under ellipsoidmetoden använder vi som mest Q- begränsningar av formen $\mathbf {a} \cdot \mathbf {y} \leq 1$ . Alla andra begränsningar kan elimineras, eftersom de inte har någon effekt på resultatet y* av ellipsoidmetoden. Vi kan eliminera ännu fler begränsningar. Det är känt att det i varje LP med m variabler finns en uppsättning m begränsningar som är tillräckliga för att bestämma den optimala lösningen (det vill säga det optimala värdet är detsamma även om endast dessa m begränsningar används). Vi kan upprepade gånger köra ellipsoidmetoden enligt ovan, varje gång vi försöker ta bort en specifik uppsättning begränsningar. Om det resulterande felet som mest är $\delta$ , tar vi bort dessa begränsningar permanent. Det kan visas att vi som mest behöver $\approx (Q/m)+m\ln(Q/m)$ elimineringar, så det ackumulerande felet är som mest $\approx \delta \cdot [(Q/m)+m\ln(Q/m)]$ . Om vi ​​provar uppsättningar av begränsningar deterministiskt, så lyckas i värsta fall en av m försök, så vi behöver köra ellipsoidmetoden som mest $\approx m\cdot [(Q/m)+m\ln(Q/m)]=Q+m^{2}\ln(Q/m )$ gånger. Om vi ​​väljer de begränsningar som ska tas bort slumpmässigt, är det förväntade antalet iterationer $O(m)\cdot [1+\ln(Q/ m)]$ .

Slutligen har vi en reducerad dubbel LP, med endast m variabler och m begränsningar. Det optimala värdet för den reducerade LP:n är åtminstone $LOPT-h$ , där $h\ ungefär \delta \cdot [(Q/m)+m\ln(Q/m)]$ .

Att lösa den ursprungliga LP:n

Med LP-dualitetssatsen är det minsta värdet för den primära LP lika med det maximala värdet för den dubbla LP, som vi betecknade med LOPT. När vi väl har en reducerad dubbel LP tar vi dess dubbla och tar en reducerad primal LP. Denna LP har bara m variabler - motsvarande endast m av C- konfigurationer. Det maximala värdet för den reducerade dubbla LP är minst $LOPT-h$ . Det kan visas ${\displaystyle LOPT+h$ att den optimala lösningen för den reducerade primala LP är som mest . Lösningen ger en i det närmaste optimal kärlpackning, med högst m konfigurationer.

Den totala körtiden för den deterministiska algoritmen, när alla objekt är större än $g\cdot B$ , är:

$O\left({\frac {Qmn}{\delta }}\cdot (Q+m^{2}\ln {\frac {Q}{m}})\right)=O\left({\frac {Q^{2}mn+Qm^{3}n\ln {\frac {Q}{m}}}{ \delta }}\right)\approx O\left(m^{8}\ln {m}\ln ^{2}({\frac {mn}{gh}})+{\frac {m^{4 }n\ln {m}}{h}}\ln({\frac {mn}{gh}})\right)$ ,

Den förväntade totala körtiden för den randomiserade algoritmen är: $O\ vänster(m^{7}\log {m}\log ^{2}({\frac {mn}{gh}})+{\frac {m^{4}n\log {m}}{h} }\log({\frac {mn}{gh}})\right)$ .

End-to-end-algoritmer

Karmarkar och Karp presenterade tre algoritmer, som använder ovanstående tekniker med olika parametrar. Körtiden för alla dessa algoritmer beror på en funktion ${\displaystyle T(\cdot ,\cdot )} ,$ som är en polynomfunktion som beskriver den tid det tar att lösa bråkdelens LP med tolerans h = 1, vilket är, för den deterministiska versionen, $T(m,n)\in O(m^{8}\log {m}\log ^{2}{n}+m^{4}n\log {m}\log {n})$ .

Algoritm 1

Låt $\epsilon >0$ vara en konstant som representerar den önskade approximationsnoggrannheten.

• 1-a. Ställ in $g=\max(1/n,\epsilon /2)$ . Låt $J$ vara en instans konstruerad från $I$ genom att ta bort alla objekt som är mindre än g .
  • 2-a. Ange $k=n\cdot \epsilon ^{2}$ . Låt $K$ vara en instans konstruerad från $J$ genom linjär gruppering med parametern k , och låt $K'$ vara den återstående instansen (gruppen av k största objekt). Observera att $m(K)\leq n/k+1\approx 1/\epsilon ^{2}$ .
    • 3-a. Konstruera det linjära konfigurationsprogrammet för ${\displaystyle K} ,$ utan integralitetsbegränsningarna.
      • 4. Beräkna en lösning x för $K$ , med tolerans h =1. Resultatet är en bråkdelpackning med $b_{L}\leq LOPT(K)+1$ fack. Körtiden är $T(m(K),n(K))\leq T(\epsilon ^{- 2},n)$ .
    • 3-b. Avrunda x till en integrallösning för $K$ . Lägg till högst $m(K)/2$ fack för bråkdelen. Det totala antalet fack är $b_{K}\leq b_{L}+m( K)/2\leq LOPT(K)+1+1/2\epsilon ^{2}$ .
  • 2-b. Packa föremålen i $K'$ med högst k fack; få en packning av $J$ . Antalet fack är $b_{J}\leq b_{K}+k\leq LOPT(K)+1+1/2\epsilon ^{2}+n\cdot \epsilon ^{2}$ .
• 1-b. Lägg till objekt som är mindre än g för att få en lösning för $I$ . Antalet fack $b_{I}\leq \max(b_{J},(1+2g)\cdot OPT(I)+1)\leq (1+\epsilon )OPT(I)+1/2\epsilon ^ {2}+3$ .

Allt som allt är antalet fack i $(1+\epsilon )OPT+O(\epsilon ^{-2})$ och körningen -tiden är i $O(n\log n+T(\epsilon ^{-2},n))$ . Genom att välja $\epsilon =OPT^{-1/3}$ får vi ${\displaystyle OPT+O(OPT$ .

Algoritm 2

Låt $g>0$ vara en reell parameter och $k>0$ en heltalsparameter som ska bestämmas senare.

• 1-a. Låt $J$ vara en instans konstruerad från $I$ genom att ta bort alla objekt som är mindre än g .
• 2. Medan $FOPT(J)>1+{\frac {k}{k-1}}\ln(1 /g)$ gör:
  • 2-a. Gör den alternativa geometriska grupperingen med parametern k . Låt $K$ vara den resulterande instansen och låt $K'$ vara den återstående instansen. Vi har $m(K)\leq FOPT(J)/k+\ln(1/g)$ .
    • 3-a. Konstruera det linjära konfigurationsprogrammet för $K$ , utan integralitetsbegränsningarna.
      • 4. Beräkna en lösning x för $K$ , med tolerans h =1. Resultatet är en bråkdelpackning med $b_{L}\leq LOPT(K)+1$ fack. Körtiden är $T(m(K), n(K))\leq T(FOPT(J)/k+\ln(1/g),n)$ .
    • 3-b. Avrunda x till en integrallösning för $K$ . Lägg inte till papperskorgar för bråkdelen. Ta istället bara bort de packade föremålen från $J$ .
  • 2-b. Packa föremålen i $K'$ i högst $2k\cdot (2+\ln(1/g))$ fack.
• 2. En gång $FOPT(J)\leq 1+{\frac {k}{k-1}}\ln( 1/g)$ , packa de återstående föremålen girigt i högst $2FOPT(J)\leq 2+{\ frac {2k}{k-1}}\ln(1/g)$ fack.
  • Vid varje iteration av slingan i steg 2 har bråkdelen av x som mest m ( K ) mönster, så $FOPT(J_{t+1})\leq m(K_{t})\leq FOPT(J_{t})/k+\ln(1/g)$ . FOPT sjunker med en faktor k i varje iteration, så antalet iterationer är som mest ${\frac {\ln FOPT(I)}{\ ln k}}+1$ .
  • $b_{J}\leq OPT(I)+\left[1+{\frac {\ln FOPT (I)}{\ln k}}\höger]\vänster[1+4k+2k\ln(1/g)\höger]+2+{\frac {2k}{k-1}}\ln(1 /g)$ det totala antalet fack som används för $J$ : .
• 1-b. Lägg till objekt som är mindre än g för att få en lösning för $I$ . Antalet fack är: $b_{I}\leq \max(b_{J},(1+ 2g)\cdot OPT(I)+1)$ .

Körtiden är i $O(n\log n+T(FOPT( J)/k+\ln(1/g),n))$ .

Om vi ​​nu väljer k =2 och g =1/FOPT(I), får vi:

${\displaystyle b_{J}\leq OPT+O(\log ^{2}(FOPT))$ ,

och följaktligen:

$_ \displaystyle b_{I}\leq \max(b_{J},OPT+2OPT/FOPT+1)\leq \max(b_{J},OPT+5)\i OPT+\log ^{2}(OPT) }$ ,

så det totala antalet fack är i ${\displaystyle OPT+O(\log ^{2}(FOPT)$ . Körtiden är $O(n\log n)+T(FOPT/2+\ln(FOPT),n)\in O(n\log {n}+T(FOPT,n))$ .

Samma algoritm kan användas med olika parametrar för att avväga körtid med noggrannhet. För vissa parameter $\alpha \in (0,1)$ , välj $k=FOPT^{\alpha }$ och $g=1/FOPT^{1-\alpha }$ . Då $\mathrm {OPT} +{\mathcal {O}}(OPT^{\alpha })$ packningen som mest körtiden är i $O(n\log {n}+T(FOPT^{(1-\alpha )},n ))$ .

Algoritm 3

Den tredje algoritmen är användbar när antalet storlekar m är litet (se även binpackning med hög multiplicitet ) .

• 1-a. Ange $g={\frac {\log ^{2}(m)}{FOPT(I)}}$ . Låt $K$ vara en instans konstruerad från $I$ genom att ta bort alla objekt som är mindre än g .
• Om $m(K)\leq FOPT(K)$ då:
  • 3-a. Konstruera det linjära konfigurationsprogrammet för $K$ , utan integralitetsbegränsningarna.
    • 4. Beräkna en lösning x för $K$ , med tolerans h =1. Resultatet är en bråkdelpackning med $b_{L}\leq LOPT(K)+1$ fack. Körtiden är $T(m(K),n(K))\leq T(\epsilon ^{- 2},n)$ .
  • 3-b. Avrunda x till en integrallösning för $K$ . Lägg inte till papperskorgar för bråkdelen. Ta istället bara bort de packade föremålen från $K$ .
• Kör steg 2 av Algoritm 2 på de återstående bitarna.
• 1-b. Lägg till objekt som är mindre än g för att få en lösning för $I$ . Antalet fack är: $b_{I}\leq \max(b_{J},(1+ 2g)\cdot OPT(I)+1)$ .

Den använder som mest $\mathrm {OPT} +{\mathcal {O}}(\log ^{2}m)$ och körtiden är i $O(n\log {n}+T(m,n))$ .

Förbättringar

KK-teknikerna förbättrades senare för att ge ännu bättre uppskattningar.

Rothvoss använder samma schema som algoritm 2, men med en annan avrundningsprocedur i steg 2. Han introducerade ett "limningssteg", där små föremål limmas ihop för att ge ett enda större föremål. Denna limning kan användas för att öka den minsta föremålsstorleken till ungefär $B/\log ^{12}(n)$ . När alla storlekar är minst $B/\log ^{12}(n)$ , kan vi ersätta $g=1/ \log ^{12}(n)$ i garantin för Algoritm 2, och få:

${J}\leq OPT(I)+O(\log(FOPT )\log(\log(n)))}$ ,

vilket ger en ${\displaystyle \mathrm {OPT} +O(\log(\mathrm {OPT} )$ fack.

Hoberg och Rothvoss använder ett liknande schema där föremålen först packas i "containrar", och sedan containrarna packas i papperskorgar. Deras algoritm behöver ${\displaystyle b_{J}\leq OPT(I)+O(\log(OPT)$ mest .