A Robust AFPTAS for Online Bin Packing with Polynomial Migration

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}$