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

Logo BII

BII

Zitieren

Zitierform:
Zitierform konnte nicht geladen werden.

Rechte

Nutzung und Vervielfältigung:Keine Creative-Commons-Lizenz - Es gelten die Bestimmungen des dt. Urheberrechts (UrhG)Bitte beachten Sie, dass einzelne Bestandteile der Publikation anderweitigen Lizenz- bzw. urheberrechtlichen Bedingungen unterliegen können.