Abstract
In a variation of bin packing called extensible bin packing, the number of bins is specified as part of the input, and bins may be extended to hold more than the usual unit capacity. The cost of a bin is 1 if it is not extended, and the size if it is extended. The goal is to pack a set of items of given sizes into the specified number of bins so as to minimize the total cost. Adapting ideas Grötschel et al. (1981), Grötschel et al. (1988), Karmarkar and Karp (1982), Murgolo (1987), we give a fully polynomial time asymptotic approximation scheme (FPTAAS) for extensible bin packing. We close with comments on the complexity of obtaining stronger results.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
Alon, N., Y. Azar, G. J. Woeginger, and T. Yadid, “Approximation schemes for scheduling on parallel machines,” Journal of Scheduling, 1, 55–66 (1998).
Coffman, Jr., E. G. and G. S. Lueker, “Approximation algorithms for extensible bin packing,” in Proceedings of the Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms, 2001, pp. 586–588.
Dell'Olmo, P., H. Kellerer, M. G. Speranza, and Z. Tuza, “A 13/12 approximation algorithm for bin packing with extendable bins,” Information Processing Letters, 65, 229–233 (1998).
Garey, M. R. and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, New York, 1979.
Grötschel M., L. Lovász, and A. Schrijver, “The ellipsoid method and its consequences in combinatorial optimization,” Combinatorica, 1(2), 169–197 (1981).
Grötschel, M., L. Lovász, and A. Schrijver, Geometric Algorithms and Combinatorial Optimization, Algorithms and Combinatorics 2. Springer-Verlag, 1988.
Hochbaum, D. S. and D. B. Shmoys, “Using dual approximation algorithms for scheduling problems: Theoretical and practical results,” journal of the ACM, 34(1), 144–162 (1987).
Karmarkar, N. and R. M. Karp, “An efficient approximation scheme for the one-dimensional bin-packing problem,” in Proceedings of the 23rd Annual Symposium on Foundations of Computer Science, 1982, pp. 312–320.
Murgolo, F. D., “An efficient approximation scheme for variable-sized bin packing,” SIAM Journal on Computing, 16(1),149–161, (1987).
Woeginger, G. J., “When does a dynamic programming formulation guarantee the existence of an FPTAS,” in Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, 1999, pp. 820–829.
Author information
Authors and Affiliations
Corresponding author
Additional information
A preliminary version of this paper appeared in the Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms, Washington, D.C., January 2001, pp. 586-588.
Rights and permissions
About this article
Cite this article
Coffman, E.G., Lueker, G.S. Approximation Algorithms for Extensible Bin Packing. J Sched 9, 63–69 (2006). https://doi.org/10.1007/s10951-006-5594-5
Issue Date:
DOI: https://doi.org/10.1007/s10951-006-5594-5