Abstrakt. Vi betraktar ett problem med fördelningen av naturresurser där vi får en uppsättning objekt, där varje objekt har en lista över par som är förknippade med det. Varje par är en konfiguration av en tillåten storlek för detta objekt, tillsammans med en icke-negativ påföljd, och ett objekt kan packas med någon konfiguration i sin lista. Målet är att välja en konfiguration för varje objekt så att antalet enhetsbehållare som behövs för att packa ihop storlekarna plus summan av påföljder minimeras. Detta problem har tillämpningar i operativsystem, bandbreddstilldelning, och diskreta tids-kostnad kompromiss planering problem. För offline-versionen av problemet designar vi en förstärkt asymptotic PTAS. Det vill säga, ett asymptotiskt approximationssystem som använder bins av storlek något större än 1. Vi överväger vidare den online avgränsade utrymme varianten, där endast ett konstant antal bins kan öppnas samtidigt. Vi utformar en sekvens av algoritmer, där sekvensen av deras konkurrensförhållanden tenderar till bästa möjliga asymptotiska konkurrensförhållande. Slutligen studerar vi bin täcker problemet, där en bin omfattas om summan av de storlekar som tilldelats det är minst 1. I denna inställning tolkas påföljder som vinst och målet är att maximera summan av vinster plus antalet täckta bins. Vi designar en algoritm med bästa möjliga konkurrensförhållande, vilket är 2. Vi generaliserar våra resultat för online-algoritmer och enhet storlek bins till fallet med variabel storlek bins, där det kan finnas flera olika storlekar av bins tillgängliga för förpackning eller täckande, och få att de konkurrensförhållanden är igen samma som för mer standard online-problem.
Correa och Epstein REF presenterade en asymptotic PTAS som använder bins av storlek något större än 1.
BIN PACKING WITH CONTROLLABLE ITEM SIZES
{'venue': 'Inf. Comput.', 'journal': 'Inf. Comput.', 'mag_field_of_study': ['Mathematics', 'Computer Science']}