Class constrained bin packing revisited. (English) Zbl 1196.68311
Summary: We study the following variant of the bin packing problem. We are given a set of items, where each item has a (non-negative) size and a color. We are also given an integer parameter \(k\), and the goal is to partition the items into a minimum number of subsets such that for each subset \(S\) in the solution, the total size of the items in \(S\) is at most 1 (as in the classical bin packing problem) and the total number of colors of the items in \(S\) is at most \(k\) (which distinguishes our problem from the classical version). We follow earlier work on this problem and study the problem in both offline and online scenarios.
MSC:
| 68W05 | Nonnumerical algorithms |
| 68W27 | Online algorithms; streaming algorithms |
| 90C27 | Combinatorial optimization |
References:
| [1] | Babel, Luitpold; Chen, Bo; Kellerer, Hans; Kotov, Vladimir, Algorithms for on-line bin-packing problems with cardinality constraints, Discrete Applied Mathematics, 143, 1-3, 238-251 (2004) · Zbl 1077.68115 |
| [2] | Caprara, Alberto; Kellerer, Hans; Pferschy, Ulrich, Approximation schemes for ordered vector packing problems, Naval Research Logistics, 92, 58-69 (2003) · Zbl 1045.90055 |
| [3] | Coffman, Edward G.; Csirik, János, Performance guarantees for one-dimensional bin packing, (Gonzalez, T. F., Handbook of Approximation Algorithms and Metaheuristics (2007), Chapman & Hall/Crc), (32-1)-(32-18), (Chapter 32) |
| [4] | de la Vega, Wenceslas Fernandez; Lueker, George S., Bin packing can be solved within 1 +epsilon in linear time, Combinatorica, 1, 4, 349-355 (1981) · Zbl 0485.68057 |
| [5] | Epstein, Leah, Online bin packing with cardinality constraints, SIAM Journal on Discrete Mathematics, 20, 4, 1015-1030 (2006) · Zbl 1130.68063 |
| [6] | Leah Epstein, Asaf Levin, AFPTAS results for common variants of bin packing: a new method to handle the small items. CoRR, abs/0906.5050, 2009.; Leah Epstein, Asaf Levin, AFPTAS results for common variants of bin packing: a new method to handle the small items. CoRR, abs/0906.5050, 2009. · Zbl 1211.68510 |
| [7] | Narendra Karmarkar, Richard 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, FOCS’82, 1982, pp. 312-320.; Narendra Karmarkar, Richard 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, FOCS’82, 1982, pp. 312-320. |
| [8] | Kellerer, Hans; Pferschy, Ulrich, Cardinality constrained bin-packing problems, Annals of Operations Research, 92, 335-348 (1999) · Zbl 0955.90106 |
| [9] | Krause, K. L.; Shen, V. Y.; Schwetman, Herbert D., Analysis of several task-scheduling algorithms for a model of multiprogramming computer systems, Journal of the ACM, 22, 4, 522-550 (1975) · Zbl 0329.68056 |
| [10] | Krause, K. L.; Shen, V. Y.; Schwetman, Herbert D., Errata: Analysis of several task-scheduling algorithms for a model of multiprogramming computer systems, Journal of the ACM, 24, 3 (1977), 527-527 |
| [11] | Lee, C. C.; Lee, Der-Tsai, A simple online bin packing algorithm, Journal of the ACM, 32, 3, 562-572 (1985) · Zbl 0629.68045 |
| [12] | Ramanan, Prakash V.; Brown, Donna J.; Lee, C. C.; Lee, Der-Tsai, On-line bin packing in linear time, Journal of Algorithms, 10, 3, 305-326 (1989) · Zbl 0682.68057 |
| [13] | Seiden, Steven S., On the online bin packing problem, Journal of the ACM, 49, 5, 640-671 (2002) · Zbl 1326.68337 |
| [14] | Shachnai, Hadas; Tamir, Tami, Polynomial time approximation schemes for class-constrained packing problems, Journal of Scheduling, 4, 6, 313-338 (2001) · Zbl 1028.90048 |
| [15] | Shachnai, Hadas; Tamir, Tami, On two class-constrained versions of the multiple knapsack problem, Algorithmica, 29, 3, 442-467 (2001) · Zbl 0969.68183 |
| [16] | Shachnai, Hadas; Tamir, Tami, Tight bounds for online class-constrained packing, Theoretical Computer Science, 321, 1, 103-123 (2004) · Zbl 1067.90144 |
| [17] | Jeffrey D. Ullman, The performance of a memory allocation algorithm. Technical Report 100, Princeton University, Princeton, NJ, 1971.; Jeffrey D. Ullman, The performance of a memory allocation algorithm. Technical Report 100, Princeton University, Princeton, NJ, 1971. |
| [18] | Vliet, André van, An improved lower bound for online bin packing algorithms, Information Processing Letters, 43, 5, 277-284 (1992) · Zbl 0764.68083 |
| [19] | Xavier, Eduardo C.; Miyazawa, Flávio Keidi, The class constrained bin packing problem with applications to video-on-demand, Theoretical Computer Science, 393, 1-3, 240-259 (2008) · Zbl 1135.68636 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
