A Robust AFPTAS for Online Bin Packing with Polynomial Migration

to full text (638 kB)   ZIP
involved person(s) / institution(s)author :
datePublished :
  • July 2012
size28 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}$.
Static URLhttps://www.uni-kiel.de/journals/receive/jportal_jparticle_00000041
IDNumber of report :
  • TR_1210