Lower bounds for several online variants of bin packing. (English) Zbl 1436.68402
Summary: We consider several previously studied online variants of bin packing and prove new and improved lower bounds on the asymptotic competitive ratios for them. For that, we use a method of fully adaptive constructions. In particular, we improve the lower bound for the asymptotic competitive ratio of online square packing significantly, raising it from roughly 1.68 to above 1.75.
MSC:
| 68W27 | Online algorithms; streaming algorithms |
| 68Q17 | Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) |
| 90C27 | Combinatorial optimization |
References:
| [1] | Angelopoulos, Spyros; Dürr, Christoph; Kamali, Shahin; Renault, Marc; Rosén, Adi, Online Bin Packing with Advice of Small Size, 40-53 (2015), Cham · Zbl 1435.68385 |
| [2] | Babel, L., Chen, B., Kellerer, H., Kotov, V.: Algorithms for on-line bin-packing problems with cardinality constraints. Discret. Appl. Math. 143(1-3), 238-251 (2004) · Zbl 1077.68115 |
| [3] | Balogh, J., Békési, J.: Semi-on-line bin packing: a short overview and a new lower bound. CEJOR 21(4), 685-698 (2013) · Zbl 1339.90272 |
| [4] | Balogh, J., Békési, J., Dósa, Gy., Epstein, L., Levin, A.: Online bin packing with cardinality constraints resolved. The Computing Res. Rep. (CoRR), arXiv:1608.06415 (2016) · Zbl 1442.68268 |
| [5] | Balogh, J., Békési, J., Dósa, Gy., Epstein, L., Levin, A.: Online bin packing with cardinality constraints resolved. In: Proceedings of the 25th Annual European Symposium on Algorithms (ESA’17), pp. 10:1-10:14 (2017) · Zbl 1442.68268 |
| [6] | Balogh, J., Békési, J., Dósa, Gy., Epstein, L., Levin, A.: A new and improved algorithm for online bin packing. In: Proceedings of the 26th annual European symposium on algorithms (ESA18), pp 5:1-5:14 (2018) · Zbl 1522.68758 |
| [7] | Balogh, J., Békési, J., Dósa, Gy., Epstein, L., Levin, A.: A new lower bound for classic online bin packing. The Computing Res. Rep. (CoRR), arXiv:1807.05554 (2018) · Zbl 1540.68320 |
| [8] | Balogh, J., Békési, J., Galambos, G.: New lower bounds for certain classes of bin packing algorithms. Theor. Comput. Sci. 440-441, 1-13 (2012) · Zbl 1247.68339 |
| [9] | Bansal, N., Correa, J., Kenyon, C., Sviridenko, M.: Bin packing in multiple dimensions Inapproximability results and approximation schemes. Math. Oper. Res. 31(1), 31-49 (2006) · Zbl 1278.90324 |
| [10] | Békési, J., Dósa, Gy., Epstein, L.: Bounds for online bin packing with cardinality constraints. Inf. Comput. 249, 190-204 (2016) · Zbl 1344.68288 |
| [11] | Blitz, D.: Lower bounds on the asymptotic worst-case ratios of on-line bin packing algorithms. M.Sc. thesis, University of Rotterdam, number 114682 (1996) |
| [12] | Boyar, J., Kamali, S., Larsen, K.S., López-Ortiz, A.: Online bin packing with advice. Algorithmica 74(1), 507-527 (2016) · Zbl 1336.68117 |
| [13] | Coppersmith, D., Raghavan, P.: Multidimensional online bin packing: Algorithms and worst case analysis. Oper. Res. Lett. 8(1), 17-20 (1989) · Zbl 0676.90050 |
| [14] | Epstein, L.: Online bin packing with cardinality constraints. SIAM J. Discret. Math. 20(4), 1015-1030 (2006) · Zbl 1130.68063 |
| [15] | Epstein, L., Imreh, Cs., Levin, A.: Class constrained bin packing revisited. Theor. Comput. Sci. 411(34-36), 3073-3089 (2010) · Zbl 1196.68311 |
| [16] | Epstein, L., Levin, A.: On bin packing with conflicts. SIAM J. Optim. 19 (3), 1270-1298 (2008) · Zbl 1175.68200 |
| [17] | Epstein, L., Levin, A.: Robust approximation schemes for cube packing. SIAM J. Optim. 23(2), 1310-1343 (2013) · Zbl 1272.68457 |
| [18] | Epstein, L., van Stee, R.: Online square and cube packing. Acta Informatica 41(9), 595-606 (2005) · Zbl 1079.68115 |
| [19] | Epstein, L., Tushia, A.: Work in progress (2018) |
| [20] | Fujiwara, H., Kobayashi, K.: Improved lower bounds for the online bin packing problem with cardinality constraints. J. Comb. Optim. 29(1), 67-87 (2015) · Zbl 1328.90125 |
| [21] | Han, X., Ye, D., Zhou, Y.: A note on online hypercube packing. CEJOR 18(2), 221-239 (2010) · Zbl 1204.90082 |
| [22] | Heydrich, S., van Stee, R.: Improved Lower Bounds for Online Hypercube Packing. The Computing Res. Rep. (CoRR), arXiv:1607.01229 (2016) · Zbl 1388.68317 |
| [23] | Johnson, D.S.: Fast algorithms for bin packing. J. Comput. Syst. Sci. 8, 272-314 (1974) · Zbl 0284.68023 |
| [24] | Johnson, D.S., Demers, A., Ullman, J.D., Garey, M.R., Graham, R.L.: Worst-case performance bounds for simple one-dimensional packing algorithms. SIAM J. Comput. 3, 256-278 (1974) · Zbl 0297.68028 |
| [25] | Kellerer, H., Pferschy, U.: Cardinality constrained bin-packing problems. Ann. Oper. Res. 92, 335-348 (1999) · Zbl 0955.90106 |
| [26] | 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) · Zbl 0329.68056 |
| [27] | Liang, F.M.: A lower bound for on-line bin packing. Inf. Process. Lett. 10(2), 76-79 (1980) · Zbl 0444.68061 |
| [28] | Seiden, S.S.: On the online bin packing problem. J. ACM 49(5), 640-671 (2002) · Zbl 1326.68337 |
| [29] | Seiden, S.S., van Stee, R.: New bounds for multi-dimensional packing. Algorithmica 36(3), 261-293 (2003) · Zbl 1045.68160 |
| [30] | Shachnai, H., Tamir, T.: Tight bounds for online class-constrained packing. Theor. Comput. Sci. 321(1), 103-123 (2004) · Zbl 1067.90144 |
| [31] | Shachnai, H., Tamir, T.: Polynomial time approximation schemes for class-constrained packing problems. J. Sched. 4(6), 313-338 (2001) · Zbl 1028.90048 |
| [32] | Ullman, J.D.: The Performance of a Memory Allocation Algorithm. Technical Report, vol. 100. Princeton University, Princeton (1971) |
| [33] | van Vliet, A.: An improved lower bound for online bin packing algorithms. Inf. Process. Lett. 43(5), 277-284 (1992) · Zbl 0764.68083 |
| [34] | Xavier, E.C., Miyazawa, F.K.: The class constrained bin packing problem with applications to video-on-demand. Theor. Comput. Sci. 393(1-3), 240-259 (2008) · Zbl 1135.68636 |
| [35] | Yao, A.C.C.: New algorithms for bin packing. J. ACM 27, 207-227 (1980) · Zbl 0434.68053 |
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.
