Problem med soptunnan

I soptäckningsproblemet måste föremål av olika storlekar packas i ett ändligt antal kärl eller behållare, som var och en måste innehålla åtminstone en viss given totalstorlek, på ett sätt som maximerar antalet kärl som används.

Det här problemet är en dubbel av problemet med papperskorgen : vid täckning av kärl är kärlstorlekarna avgränsade underifrån och målet är att maximera antalet; vid sopförpackning är kärlstorlekarna avgränsade uppifrån och målet är att minimera antalet.

Problemet är NP-hårt , men det finns olika effektiva approximationsalgoritmer :

• Algoritmer som täcker minst 1/2, 2/3 eller 3/4 av det optimala antalet fack asymptotiskt och löper i tiden $O( n),O(n\log n),O(n{\log}^{2}n)$ respektive.
• En asymptotisk PTAS , algoritmer med begränsat värsta tänkbara beteende vars förväntade beteende är asymptotiskt optimalt för vissa diskreta distributioner, och en inlärningsalgoritm med asymptotiskt optimalt förväntat beteende för alla diskreta distributioner.
• En asymptotisk FPTAS .

Algoritmen för dubbelriktad påfyllning av fack

Csirik, Frenk, Lebbe och Zhang presenterar följande enkla algoritm för 2/3 approximation. Anta att papperskorgen är 1 och det finns n objekt.

• Beställ artiklarna från den största (1) till den minsta ( n ).
• Fyll ett fack med de största objekten : 1, 2, ..., m , där m är det största heltal för vilket summan av objekt 1, ..., m är mindre än 1.
• Lägg till de minsta föremålen : n , n -1, ..., tills dess värde höjs över 1.

För alla fall I , beteckna med $\mathrm {OPT} (I)$ antalet fack i den optimala lösningen och med $\mathrm {BDF} (I)$ antalet fulla fack i den dubbelriktade fyllningsalgoritmen. Sedan $\mathrm {BDF} (I)\geq (2/3)\mathrm {OPT} (I )-(2/3)$ , eller motsvarande, $\mathrm {OPT} (I)\leq (3/2) \mathrm {BDF} (I)+1$ .

bevis

För beviset används följande terminologi.

• $t:=\mathrm {BDF} (I)=$ antalet fack som fylls av algoritmen.
• $B_{1},\ldots ,B_{t}:=$ t - facken fyllda av algoritmen.
• Inledande artiklar - de t objekten som infogas först i var och en av t- fackarna.
• Slutliga föremål - de t föremål som infogas sist i var och en av t- fackarna.
• Mellanposter - alla föremål som varken är initiala eller slutgiltiga.
• $w$ := antalet slutföremål som är högst 1/2 (motsvarande är $tw$ antalet slutföremål större än 1/2).

Summan av varje fack $B_{1},\ldots ,B_{t}$ är minst 1, men om den slutliga artikeln tas bort från den är den återstående summan mindre än 1. Var och en av de första $w$ -facken $B_{1},\ldots ,B_{w}$ innehåller ett initialt objekt, möjligen några mellanobjekt, och ett sista objekt . Vart och ett av de sista $tw$ -facken $B_{w+1},\ldots ,B_{t}$ innehåller endast ett initialt objekt och ett sista objekt, eftersom båda är större än 1/2 och deras summa redan är större än 1.

Beviset tar hänsyn till två fall.

Det enkla fallet är $w=t$ , det vill säga alla slutartiklar är mindre än 1/2. Sedan är summan av varje ifylld $B_{i}$ högst 3/2, och summan av återstående poster är högst 1, så summan av alla poster är högst $3t/2+1$ . Å andra sidan, i den optimala lösningen $\mathrm {OPT} (I)$ minst 1, så summan av alla objekt är minst . Därför, $\mathrm {OPT} (I)\leq 3t/2+1$ efter behov.

Det hårda fallet är $w<t$ , det vill säga vissa slutartiklar är större än 1/2. Vi bevisar nu en övre gräns på $\mathrm {OPT} (I)$ genom att presentera den som en summa $\mathrm {OPT} (I)=|K_{0}|+|K_{1}|+|K_{2}|$ där:

• $K_{0}:=$ de optimala papperskorgen utan initiala/slutliga föremål (endast mellanobjekt).
• $K_{1}:=$ de optimala papperskorgen med exakt en initial/avslutande artikel (och några mellanobjekt).
• $K_{2}:=$ de optimala lådorna med två eller flera initiala/slutliga objekt (och några mellanobjekt).

Vi fokuserar först på de optimala fackarna i $K_{0}$ och $K_{1}$ . Vi presenterar en bijektion mellan objekten i varje sådant fack till några objekt i $B_{1},\ldots ,B_{t}$ som är minst lika värdefulla.

• Det enda initiala/slutliga objektet i $B_{1},\ldots ,B_{|K_{1}|}$$\displaystyle K_{1}}$ -fack mappas till det initiala objektet i . Observera att dessa är de största initiala föremålen.
• Mellanposterna i ${\displaystyle K_{0}}-$ och ${\displaystyle K_{1}} -fack$$B_{1},\ldots ,B_{w}$ mappade till mellanposterna i . Observera att dessa papperskorgar innehåller alla de mittersta föremålen.
• Därför mappas alla poster i $K_{0}}$$B_{1},\ldots ,B_{|K_{1}|}$ och ${\displaystyle K_{1}} till alla icke-slutliga poster i$ , plus alla mittposter i $B_{|K_{1}|+1},\ldots ,B_{w}$ .
• Summan av varje fack $B_{1},\ldots ,B_{w}$ utan dess slutliga artikel är mindre än 1. Dessutom är den initiala artikeln mer än 1/2, så summan av endast de mellersta posterna är mindre än 1/2. Därför summan av alla icke-slutliga poster i $B_{1},\ldots ,B_{|K_{1}|}$ , plus alla mittposter i ${\displaystyle B_{|K_{1}|+1},\ldots ,B_{w}} ,$ är högst $|K_{1}|+(w-|K_{1}|)/2=(|K_{1 }|+w)/2$ .
• Summan av varje optimal bin är minst 1. Därför: ${\displaystyle |K_{0}|+|K_{1}|\leq (|K_{1}|+w)/2} ,$ vilket innebär $2|K_{0}|+|K_{1}|\leq w\leq t$ .

Vi fokuserar nu på de optimala fackarna i $K_{1}$ och $K_{2}$ .

• Det totala antalet initiala/slutliga artiklar i $K_{1}$ och $K_{2}$ fack är minst $|K_{1}|+2|K_{2}|$ , men deras totala antal är också $2t$ eftersom det finns exakt två initiala/slutliga objekt i varje fack. Därför $|K_{1}|+2|K_{2}|\leq 2t$ .
• Att summera de två sistnämnda olikheterna innebär att $\displaystyle 2\mathrm {OPT} (I)\leq 3t} ,$$\mathrm {OPT} (I)\leq 3t/2$ vilket innebär .

2/3-faktorn är snäv för BDF. Tänk på följande instans (där $\epsilon >0$ är tillräckligt liten):

$${\begin{aligned}1-6k\ epsilon ,~&~{\tfrac {1}{2}}-\epsilon ,\ldots ,{\tfrac {1}{2}}-\epsilon ,~&~\epsilon ,\ldots ,\epsilon \\~ &~\{\cdots 6k~{\text{enheter}}\cdots \}~&~\{\cdots 6k~{\text{enheter}}\cdots \}\end{aligned}}$$

BDF initierar det första facket med det största föremålet och fyller det med de $6k$ minsta objekten. Sedan kan de återstående $6k$ objekten endast täcka fack i trillingar, så allt som allt är $2k+1$ fack fyllda. Men i OPT kan man fylla $3k$ fack, som var och en innehåller två av medelstora föremål och två små föremål.

Tre-klassers bin-filling-algoritm

Csirik, Frenk, Lebbe och Zhang presenterar en annan algoritm som uppnår en 3/4 approximation. Algoritmen ordnar objekten från stora till små och delar upp dem i tre klasser:

• X: Varorna med storleken minst 1/2;
• Y: Artiklar med storlek mindre än 1/2 och minst 1/3;
• Z: Artiklar med storlek mindre än 1/3.

Algoritmen fungerar i två faser. Fas 1:

• Initiera en ny papperskorg med antingen det största föremålet i X, eller de två största föremålen i Y, beroende på vilket som är störst. Observera att i båda fallen är den initiala papperskorgssumman mindre än 1.
• Fyll den nya behållaren med föremål från Z i ökande värdeordning.
• Upprepa tills antingen XUY eller Z är tomma.

Fas 2:

• Om XUY är tom, fyll papperskorgar med föremål från Z enligt den enkla nästa-passningsregeln.
• Om Z är tom, packa de återstående föremålen i X parvis och de som återstår i Y i tripletter.

I exemplet ovan, som visar tätheten hos BDF, är uppsättningarna:

$${\begin{aligned}1-6k\epsilon ,~&~{\tfrac {1}{2}}-\epsilon ,\ldots ,{\tfrac {1}{2}} -\epsilon ,~&~\epsilon ,\ldots ,\epsilon \\\{|X|=1\}~&~\{\cdots |Y|=6k\cdots \}~&~\{\cdots | Z|=6k\cdots \}\end{aligned}}$$

TCF uppnår det optimala resultatet, eftersom det initierar alla $3k$ fack med par av objekt från Y och fyller dem med par av objekt från Z.

För alla fall I , beteckna med $\mathrm {OPT} (I)$ antalet fack i den optimala lösningen och med $(I)}$${\displaystyle \mathrm {TCF$ antalet fulla fack i fyllningsalgoritmen med tre klasser. Sedan ${\displaystyle \mathrm {TCF} (I)\geq (3/4)(\mathrm {OPT} (I$ .

3/4-faktorn är snäv för TCF. Tänk på följande instans (där $\epsilon >0$ är tillräckligt liten):

$$\displaystyle {\} start{aligned}{\tfrac {1}{2}}-6k\epsilon ,{\tfrac {1}{2}}-6k\epsilon ,~&~{\tfrac {1}{3}}-\epsilon ,\ldots ,{\tfrac {1}{3}}-\epsilon ,~&~\epsilon ,\ldots ,\epsilon \\~&~\{\cdots 12k~{\text{enheter}}\cdots \ }~&~\{\cdots 12k~{\text{enheter}}\cdots \}\end{aligned}}}$$

TCF initierar det första facket med de två största objekten och fyller det med de $12 k$ minsta objekten. Sedan kan de återstående $12k$ objekten endast täcka fack i grupper om fyra, så allt som allt är $3k+1$ fack fyllda. Men i OPT kan man fylla $4k$ fack, som var och en innehåller 3 medelstora föremål och 3 små föremål.

Polynom-tidsapproximationsscheman

Csirik, Johnson och Kenyon presenterar en asymptotisk PTAS. Det är en algoritm som, för varje ε >0, fyller minst $(1-5\varepsilon )\cdot \mathrm {OPT} (I) -4$ fack om summan av alla poster är mer än $13B/\epsilon ^{3}$ , och minst ${ \displaystyle (1-2\varepsilon )\cdot \mathrm {OPT} (I)-1}$ annars. Den körs i tiden $O(n^{1/\varepsilon ^{2}})$ . Algoritmen löser en variant av det linjära konfigurationsprogrammet , med $n^{1/\varepsilon ^{2}}$ variabler och $1+1/\varepsilon ^{2}$ begränsningar. Denna algoritm är bara teoretiskt intressant, eftersom för att få bättre än 3/4 approximation måste vi ta ${\displaystyle \varepsilon <1/20} ,$ och då är antalet variabler mer än ${ \displaystyle n^{400}}$ .

De presenterar också algoritmer för onlineversionen av problemet. I online-inställningen är det inte möjligt att få en asymptotisk approximationsfaktor i värsta fall bättre än 1/2. Det finns dock algoritmer som fungerar bra i genomsnittsfallet.

Jansen och Solis-Oba presenterar en asymptotisk FPTAS. Det är en algoritm som, för varje ε >0, fyller minst $(1-\varepsilon )\cdot \mathrm {OPT} (I)-1$ bins om summan av alla objekt är mer än $13B/\epsilon ^{3}$ (om summan av objekt är mindre än så är optimum högst $13/\epsilon ^{3}\in O(1/\epsilon ^{3})$ i alla fall). Den går i tid $\{displaystyle O\left \frac {1}{\epsilon ^{5}}}\cdot \ln {\frac {n}{\varepsilon }}\cdot \max {(n^{2},{\frac {1}{\varepsilon }}\ln \ln {\frac {1}{\varepsilon ^{3}}})}+{\frac {1}{\varepsilon ^{4}}}{\mathcal {T_{M}}}( {\frac {1}{\varepsilon ^{2}}})\right)}$${\mathcal {T_{M}}}(n)$ där är körtidskomplexiteten för bästa tillgängliga algoritm för matrisinversion (för närvarande runt ${\displaystyle O(n^{2.38})} )$ . Denna algoritm blir bättre än 3/4 approximationen redan när $\displaystyle \varepsilon <1/4} , och i detta fall är$ rimliga - ca $2^ {10}n^{2}+2^{18}$ .

Relaterade problem

I problemet med tilldelning av rättvisa föremål finns det olika personer som var och en tillskriver varje föremål olika värde. Målet är att tilldela varje person en "bin" full med föremål, så att värdet på varje papperskorg är åtminstone en viss konstant, och så många som möjligt får en papperskorg. Många tekniker från tunntäckning används också i detta problem.

Genomföranden

• Python: Paketet prtpy innehåller en implementering av Csirik-Frenk-Labbe-Zhang-algoritmerna .