Abstrakt. Vi studerar den multidimensionella generaliseringen av det klassiska Bin Packing problemet: Med tanke på en samling d-dimensionella rektanglar av angivna storlekar, är målet att packa dem i det minsta antalet enhet kuber. En lång historia av resultat finns för detta problem och dess speciella fall. För närvarande uppnår den mest kända approximationsalgoritmen för förpackning av tvådimensionella rektanglar en garanti på 1,69 i det asymptotiska fallet (dvs. när den optimala använder ett stort antal bins) [3]. En viktig öppen fråga har varit om 2-dimensionell bin packning i huvudsak liknar det 1-dimensionella fallet eftersom det medger en asymptotisk polynom tid approximation system (APTAS) [12, 17] eller inte. Vi svarar på frågan i negativ och visar att problemet är APX hårt i asymptotisk mening. På den positiva sidan ger vi följande resultat: För det första anser vi att specialfallet där vi måste packa d-dimensionella kuber i det minsta antalet enhet kuber. Vi ger en asymptotisk polynom tid approximation system för detta problem. Detta innebär en betydande förbättring jämfört med den tidigare mest kända asymptotiska approximationsfaktorn 2 − (2/3), och löser problemets approximabilitet. För det andra, vi ger en polynom tid algoritm för att packa godtyckliga rektanglar i som mest OPT fyrkantiga bins med sidor av längd 1 + ε, där OPT betecknar det minsta antalet enhet bins som krävs för att packa dessa rektanglar. Intressant nog har detta resultat inte en additiv konstant term d.v.s. är inte ett asymptotiskt resultat. Som en följd får vi en polynom tid approximation system för problemet med att placera en samling av rektanglar i en minsta area innesluta rektangel, lösa även approximabiliteten av detta problem.
För den flerdimensionella fall av förpackning hyperkuber, det finns en APTAS REF, och det visas också att det finns en algoritm som packar (tvådimensionella) rektanglar i det optimala antalet bins med resursförstärkning.
Bin packing in multiple dimensions: Inapproximability results and approximation schemes
{'venue': 'MATHEMATICS OF OPERATIONS RESEARCH', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}