ABSTRACT
We illustrate the concept of asymptotic (fully) polynomial-time approximation schemes (APTAS, AFPTAS) via a study of the bin packing problem. We discuss in detail an APTAS due to Fernandez de la Vega and Lueker [1] and an AFPTAS due to Karmakar and Karp [2]. Many of the algorithmic and analytical techniques described in this chapter can be applied elsewhere in the development and study of other polynomial-time approximation schemes. We conclude with a brief survey of other bin packing-related results and other examples of APTAS and AFPTAS.
