Asymptotic Polynomial-Time Approximation Schemes. Handbook of Approximation Algorithms and Metaheuristics.
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.
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
