Asymptotic Approximation Schemes for the Concave Cost Bin Packing Problem

摘要

In this paper, we present an asymptotic linear time approximation scheme and an asymptotic full polynomial time approximation scheme for the concave cost bin packing problem, in which the cost of each bin is a nondecreasing concave function of the bin utilization.