×

Bin packing with controllable item sizes. (English) Zbl 1169.90018

Summary: We consider a natural resource allocation problem in which we are given a set of items, where each item has a list of pairs associated with it. Each pair is a configuration of an allowed size for this item, together with a nonnegative penalty, and an item can be packed using any configuration in its list. The goal is to select a configuration for each item so that the number of unit bins needed to pack the sizes plus the sum of penalties is minimized. This problem has applications in operating systems, bandwidth allocation, and discrete time-cost tradeoff planning problems.
For the offline version of the problem we design an augmented asymptotic PTAS. That is, an asymptotic approximation scheme that uses bins of size slightly larger than 1. We further consider the online bounded space variant, where only a constant number of bins can be open simultaneously. We design a sequence of algorithms, where the sequence of their competitive ratios tends to the best possible asymptotic competitive ratio. Finally, we study the bin covering problem, in which a bin is covered if the sum of sizes allocated to it is at least 1. In this setting, penalties are interpreted as profits and the goal is to maximize the sum of profits plus the number of covered bins. We design an algorithm of best possible competitive ratio, which is 2. We generalize our results for online algorithms and unit sized bins to the case of variable sized bins, where there may be several distinct sizes of bins available for packing or covering, and get that the competitive ratios are again the same as for the more standard online problems.

MSC:

90C27 Combinatorial optimization
68W25 Approximation algorithms
68W40 Analysis of algorithms
90C59 Approximation methods and heuristics in mathematical programming
91B32 Resource and cost allocation (including fair division, apportionment, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Assmann, S. F.; Johnson, D. S.; Kleitman, D. J.; Leung, J. Y.-T., On a dual version of the one-dimensional bin packing problem, Journal of Algorithms, 5, 502-525 (1984) · Zbl 0556.68011
[2] Bansal, N.; Correa, J. R.; Kenyon, C.; Sviridenko, M., Bin packing in multiple dimensions: inapproximability results and approximation schemes, Mathematics of Operations Research, 31, 31-49 (2006) · Zbl 1278.90324
[3] Bein, W.; Correa, J. R.; Han, X., A fast asymptotic approximation scheme for bin packing with rejection, Theoretical Computer Science, 393, 14-22 (2008) · Zbl 1136.68057
[4] Caprara, A.; Kellerer, H.; Pferschy, U., Approximation schemes for ordered vector packing problems, Naval Research Logistics, 92, 58-69 (2003) · Zbl 1045.90055
[5] M. Chlebík, Janka Chlebíková, Inapproximability results for orthogonal rectangle packing problems with rotations, in: Proceedings of the 6th Italian Conference on Algorithms and Complexity (CIAC2006), 2006, pp. 199-210.; M. Chlebík, Janka Chlebíková, Inapproximability results for orthogonal rectangle packing problems with rotations, in: Proceedings of the 6th Italian Conference on Algorithms and Complexity (CIAC2006), 2006, pp. 199-210.
[6] Coffman, E. G.; Garey, M. R.; Johnson, D. S., Approximation algorithms for bin packing: a survey, (Hochbaum, D., Approximation Algorithms (1997), PWS Publishing Company) · Zbl 0558.68062
[7] Csirik, J., An online algorithm for variable-sized bin packing, Acta Informaticae, 26, 697-709 (1989) · Zbl 0689.68047
[8] Csirik, J.; Totik, V., On-line algorithms for a dual version of bin packing, Discrete Applied Mathematics, 21, 163-167 (1988) · Zbl 0659.68069
[9] J. Csirik, G. J. Woeginger, On-line packing and covering problems, in: A. Fiat, G. J. Woeginger (Eds.), Online Algorithms: The State of the Art, 1998, pp. 147-177.; J. Csirik, G. J. Woeginger, On-line packing and covering problems, in: A. Fiat, G. J. Woeginger (Eds.), Online Algorithms: The State of the Art, 1998, pp. 147-177.
[10] De, P.; Dunne, E. J.; Ghosh, J. B.; Wells, C. E., Complexity of the discrete time-cost tradeoff problem for project networks, Opererations Research, 45, 302-306 (1997) · Zbl 0893.90086
[11] Fernandez de la Vega, W.; Lueker, G. S., Bin packing can be solved within \(1 + \operatorname{\&z.epsiv;}\) in linear time, Combinatorica, 1, 349-355 (1981) · Zbl 0485.68057
[12] Dósa, G.; He, Y., Bin packing problems with rejection penalties and their dual problems, Information and Computation, 204, 795-815 (2006) · Zbl 1110.68172
[13] L. Epstein, Bin packing with rejection revisited, Algorithmica, in press.; L. Epstein, Bin packing with rejection revisited, Algorithmica, in press. · Zbl 1129.68585
[14] L. Epstein, A. Levin, AFPTAS results for common variants of bin packing: a new method to handle the small items, Manuscript.; L. Epstein, A. Levin, AFPTAS results for common variants of bin packing: a new method to handle the small items, Manuscript. · Zbl 1211.68510
[15] Friesen, D. K.; Langston, M. A., Variable sized bin packing, SIAM Journal on Computing, 15, 222-230 (1986) · Zbl 0589.68036
[16] Hochbaum, D. S.; Shmoys, D. B., Using dual approximation algorithms for scheduling problems: theoretical and practical results, Journal of the ACM, 34, 144-162 (1987)
[17] Johnson, D. S.; Demers, A.; Ullman, J. D.; Garey, Michael R.; Graham, Ronald L., Worst-case performance bounds for simple one-dimensional packing algorithms, SIAM Journal on Computing, 3, 256-278 (1974)
[18] Johnson, D. S., Fast algorithms for bin packing, Journal of Computer and System Sciences, 8, 272-314 (1974) · Zbl 0284.68023
[19] N. Karmarkar, 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.; N. Karmarkar, 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.
[20] Lee, C. C.; Lee, D. T., A simple online bin packing algorithm, Journal of the ACM, 32, 562-572 (1985) · Zbl 0629.68045
[21] Lenstra, H. W., Integer programming with a fixed number of variables, Mathematics of Operations Research, 8, 538-548 (1983) · Zbl 0524.90067
[22] Ramanan, P.; Brown, D. J.; Lee, C. C.; Lee, D. T., Online bin packing in linear time, Journal of Algorithms, 10, 305-326 (1989) · Zbl 0682.68057
[23] Seiden, S. S., An optimal online algorithm for bounded space variable-sized bin packing, SIAM Journal on Discrete Mathematics, 14, 458-470 (2001) · Zbl 0992.68248
[24] Seiden, S. S., On the online bin packing problem, Journal of the ACM, 49, 640-671 (2002) · Zbl 1326.68337
[25] Seiden, S. S.; van Stee, R.; Epstein, L., New bounds for variable-sized online bin packing, SIAM Journal on Computing, 32, 455-469 (2003) · Zbl 1029.68084
[26] Skutella, M., Approximation algorithms for the discrete time-cost tradeoff problem, Mathematics of Operations Research, 23, 909-929 (1998) · Zbl 0977.90016
[27] J. D. Ullman, The performance of a memory allocation algorithm, Tech. Report 100, Princeton University, Princeton, NJ, 1971.; J. D. Ullman, The performance of a memory allocation algorithm, Tech. Report 100, Princeton University, Princeton, NJ, 1971.
[28] van Vliet, A., An improved lower bound for online bin packing algorithms, Information Processing Letters, 43, 277-284 (1992) · Zbl 0764.68083
[29] Woeginger, G. J., Improved space for bounded-space online bin packing, SIAM Journal on Discrete Mathematics, 6, 575-581 (1993) · Zbl 0806.90068
[30] Woeginger, G. J., There is no asymptotic ptas for two-dimensional vector packing, Information Processing Letters, 64, 293-297 (1997) · Zbl 1338.68122
[31] Woeginger, G. J.; Zhang, G., Optimal on-line algorithms for variable-sized bin covering, Operations Research Letters, 25, 47-50 (1999) · Zbl 0941.90073
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.