Abstract
We continue the study of bin packing with splittable items and cardinality constraints. In this problem, a set of n items must be packed into as few bins as possible. Items may be split, but each bin may contain at most k (parts of) items, where k is some given parameter. Complicating the problem further is the fact that items may be larger than 1, which is the size of a bin. The problem is known to be strongly NP-hard for any fixed value of k.
We essentially close this problem by providing an efficient polynomial-time approximation scheme (EPTAS) for most of its versions. Namely, we present an efficient polynomial time approximation scheme for k=o(n). A PTAS for k=Θ(n) does not exist unless P = NP.
Additionally, we present dual approximation schemes for k=2 and for constant values of k. Thus we show that for any ε>0, it is possible to pack the items into the optimal number of bins in polynomial time, if the algorithm may use bins of size 1+ε.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Babel, L., Chen, B., Kellerer, H., Kotov, V.: Algorithms for on-line bin-packing problems with cardinality constraints. Discrete Appl. Math. 143(1–3), 238–251 (2004)
Caprara, A., Kellerer, H., Pferschy, U.: Approximation schemes for ordered vector packing problems. Nav. Res. Logist. 92, 58–69 (2003)
Cesati, M., Trevisan, L.: On the efficiency of polynomial time approximation schemes. Inf. Process. Lett. 64(4), 165–171 (1997)
Chung, F., Graham, R., Mao, J., Varghese, G.: Parallelism versus memory allocation in pipelined router forwarding engines. Theory Comput. Syst. 39(6), 829–849 (2006)
de la Vega, W.F., Lueker, G.S.: Bin packing can be solved within 1 + epsilon in linear time. Combinatorica 1(4), 349–355 (1981)
Frank, A., Tardos, É.: An application of simultaneous Diophantine approximation in combinatorial optimization. Combinatorica 7(1), 49–65 (1987)
Epstein, L.: Online bin packing with cardinality constraints. SIAM J. Discrete Math. 20(4), 1015–1030 (2006)
Epstein, L., Levin, A.: AFPTAS results for common variants of bin packing: a new method to handle the small items. SIAM J. Optim. (2010, in press)
Epstein, L., van Stee, R.: Approximation schemes for packing splittable items with cardinality constraints. In: Proc. of the 5th International Workshop on Approximation and Online Algorithms (WAOA2007), pp. 232–245 (2007)
Epstein, L., van Stee, R.: Improved results for a memory allocation problem. In: Proc. of the 10th International Workshop on Algorithms and Data Structures (WADS2007), pp. 362–373 (2007). Also in Theory Comput. Syst. (to appear)
Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, New York (1979)
Graham, R.L., Mao, J.: Parallel resource allocation of splittable items with cardinality constraints. Preprint (2006)
Hochbaum, D.S., Shmoys, D.B.: Using dual approximation algorithms for scheduling problems: theoretical and practical results. J. ACM 34(1), 144–162 (1987)
Karmarkar, N., Karp, R.M.: An efficient approximation scheme for the one-dimensional bin-packing problem. In: Proceedings of the 23rd Annual Symposium on Foundations of Computer Science, pp. 312–320 (1982)
Kellerer, H., Pferschy, U.: Cardinality constrained bin-packing problems. Ann. Oper. Res. 92, 335–348 (1999)
Krause, K.L., Shen, V.Y., Schwetman, H.D.: Analysis of several task-scheduling algorithms for a model of multiprogramming computer systems. J. ACM 22(4), 522–550 (1975)
Krause, K.L., Shen, V.Y., Schwetman, H.D.: Errata: “Analysis of several task-scheduling algorithms for a model of multiprogramming computer systems”. J. ACM 24(3), 527–527 (1977)
Shachnai, H., Tamir, T., Yehezkely, O.: Approximation schemes for packing with item fragmentation. Theory Comput. Syst. 43(1), 81–98 (2008)
Shachnai, H., Yehezkely, O.: Fast asymptotic FPTAS for packing fragmentable items with costs. In: Proc. of the 16th International Symposium on Fundamentals of Computation Theory (FCT2007), pp. 482–493 (2007)
Simchi-Levi, D.: New worst-case results for the bin-packing problem. Nav. Res. Logist. 41(4), 579–585 (1994)
Author information
Authors and Affiliations
Corresponding author
Additional information
Some of the results in this paper (for constant k) have appeared in the extended abstract [9].
Research of R. van Stee was supported by the Alexander von Humboldt Foundation and the German Research Society (DFG).
Rights and permissions
About this article
Cite this article
Epstein, L., Levin, A. & van Stee, R. Approximation Schemes for Packing Splittable Items with Cardinality Constraints. Algorithmica 62, 102–129 (2012). https://doi.org/10.1007/s00453-010-9445-6
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00453-010-9445-6