ABSTRACT
This chapter illustrates the concept of asymptotic polynomial-time approximation schemes via a study of the bin packing problem. 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 (PTASs). The algorithmic and analytic tools demonstrated here are widely applicable to the study and development of approximation schemes. The final ingredient needed for the polynomial-time approximation schemes (AFPTAS, APTAS) is called interval partitioning or linear grouping. The basic idea behind the AFPTAS of N. Karmakar and R. M. Karp is very similar to that used in the APTAS. The chapter concludes by presenting a literature survey on topics related to bin packing and asymptotic approximation schemes. There are other problems that admit absolute approximation algorithms, that is, algorithms guaranteed to produce solutions whose costs are at most an additive constant away from the optimal.
