A Robust AFPTAS for Online Bin Packing with Polynomial Migration

zum Volltext (638 kB)   ZIP
Beteiligte Person(en) / Institution(en)Autor :
DatumErschienen :
  • Juli 2012
Seitenbereich28 S.

In this paper we develop general LP and ILP techniques to improve an approximate solution by changing an existing solution only by a small amount. We apply these techniques to the online bin packing problem, where we allow additionally to repack a constant amount of items (called migration factor) whenever a new item arrives. As a result we obtain a robust asymptotic fully polynomial time approximation scheme (AFPTAS) with migration factor, that is polynomial in $\frac{1}{\epsilon}$. To our knowledge this is the first (asymptotic) approximation scheme of a NP-hard problem having a polynomial migration factor in $\frac{1}{\epsilon}$. Our result improves the robust APTAS of Epstein and Levin, which has a running time that is double exponential in $\frac{1}{\epsilon}$ and exponential migration factor in $\frac{1}{\epsilon}$.
Statische URLhttps://www.uni-kiel.de/journals/receive/jportal_jparticle_00000041
IDNummer des Berichts :
  • TR_1210