Google Research

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)

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.

Learn more about how we do research

We maintain a portfolio of research projects, providing individuals and teams the freedom to emphasize specific types of work