Jump to Content

Asymptotic Polynomial-Time Approximation Schemes. Handbook of Approximation Algorithms and Metaheuristics.

Rajeev Motwani
Liadan O'Callaghan
An Zhu
Handbook of Approximation Algorithms and Metaheuristics, Teofilo Gonzalez, ed., Chapman and Hall/CRC (2007)
Google Scholar

Abstract

Approximation schemes are presented for BIN PACKING, including a PAS due to Vega and Lueker, and an FPAS due to Karmakar and Karp. It is shown that the latter can be modified into an approximation algorithm whose absolute error is bounded by a poly-logarithmic function in the value of the optimal solution.

Research Areas