Adaptive Bin Packing with Overflow

References

• [1] Alaei S, Hajiaghayi M, Liaghat V (2013) The online stochastic generalized assignment problem. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Springer, Berlin), 11–25.Crossref, Google Scholar
• [2] Albers S (2003) Online algorithms: A survey. Math. Programming 97(1–2):3–26.Crossref, Google Scholar
• [3] Balogh J, Békési J, Galambos G (2012) New lower bounds for certain classes of bin packing algorithms. Theoret. Comput. Sci. 440:1–13.Crossref, Google Scholar
• [4] Balogh J, Békési J, Dósa G, Epstein L, Levin A (2018) A new and improved algorithm for online bin packing. Azar Y, Bast H, Herman G, eds. Proc. 26th Annual Eur. Sympos. on Algorithms (Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Helsinki, Finland), 112:5:1–5:14.Google Scholar
• [5] Balseiro S, Brown D (2019) Approximations to stochastic dynamic programs via information relaxation duality. Oper. Res. 67:577–597.Abstract, Google Scholar
• [6] Bhalgat A, Goel A, Khanna S (2011) Improved approximation results for stochastic knapsack problems. Proc. 22nd Annual ACM-SIAM Sympos. on Discrete Algorithms (SIAM, Philadelphia), 1647–1665.Google Scholar
• [7] Blado D, Toriello A (2019) Relaxation analysis for the dynamic knapsack problem with stochastic item sizes. SIAM J. Optim. 29:1–30.Crossref, Google Scholar
• [8] Blado D, Toriello A (2021) A column and constraint generation algorithm for the dynamic knapsack problem with stochastic item sizes. Math. Programming Comput. 13:185–223.Crossref, Google Scholar
• [9] Blado D, Hu W, Toriello A (2016) Semi-infinite relaxations for the dynamic knapsack problem with stochastic item sizes. SIAM J. Optim. 26:1625–1648.Crossref, Google Scholar
• [10] Borodin A, El-Yaniv R (2005) Online Computation and Competitive Analysis (Cambridge University Press, Cambridge, UK).Google Scholar
• [11] Christensen HI, Khan A, Pokutta S, Tetali P (2017) Approximation and online algorithms for multidimensional bin packing: A survey. Comput. Sci. Rev. 24:63–79. Google Scholar
• [12] Coffman EG Jr, Lueker GS (2001) Approximation algorithms for extensible bin packing. Kosaraju SR, ed. Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, (ACM/SIAM, Washington, DC), 586–588.Google Scholar
• [13] Coffman EG Jr, Garey MR, Johnson DS (1978) An application of bin-packing to multiprocessor scheduling. SIAM J. Comput. 7(1):1–17.Crossref, Google Scholar
• [14] Coffman E Jr, Garey M, Johnson D (1996) Approximation algorithms for bin packing: A survey. Approximation Algorithms for NP-Hard Problems, 46–93.Google Scholar
• [15] Coffman EG Jr, So K, Hofri M, Yao A (1980) A stochastic model of bin-packing. Inf. Control. 44(2):105–115.Crossref, Google Scholar
• [16] Coffman EG Jr, Courcoubetis C, Garey MR, Johnson DS, Shor PW, Weber RR, Yannakakis M (2000) Bin packing with discrete item sizes, part i: Perfect packing theorems and the average case behavior of optimal packings. SIAM J. Discrete Math. 13(3):384–402.Crossref, Google Scholar
• [17] Csirik J, Johnson DS, Kenyon C, Orlin JB, Shor PW, Weber RR (2006) On the sum-of-squares algorithm for bin packing. J. ACM 53(1):1–65.Crossref, Google Scholar
• [18] De La Vega WF, Lueker GS (1981) Bin packing can be solved within 1+ ε in linear time. Combinatorica 1(4):349–355.Crossref, Google Scholar
• [19] Dean BC, Goemans MX, Vondrák J (2005) Adaptivity and approximation for stochastic packing problems. Proc. Sixteenth Annual Sympos. Discrete Algorithms (SODA 2005), Vancouver, British Columbia (SIAM), 5:395–404.Google Scholar
• [20] Dean BC, Goemans MX, Vondrák J (2008) Approximating the stochastic knapsack problem: The benefit of adaptivity. Math. Oper. Res. 33(4):945–964.Link, Google Scholar
• [21] Della Vedova ML, Tessera D, Calzarossa MC (2016) Probabilistic provisioning and scheduling in uncertain cloud environments. Proc. IEEE Sympos. on Comput. and Comm. (IEEE, New York), 797–803.Google Scholar
• [22] Dell’Olmo P, Kellerer H, Speranza MG, Tuza Z (1998) A 1312 approximation algorithm for bin packing with extendable bins. Inform. Processing Lett. 65(5):229–233.Crossref, Google Scholar
• [23] Denton BT, Miller AJ, Balasubramanian HJ, Huschka TR (2010) Optimal allocation of surgery blocks to operating rooms under uncertainty. Oper. Res. 58(4-part-1):802–816.Link, Google Scholar
• [24] Derman C, Lieberman GJ, Ross SM (1978) A renewal decision problem. Management Sci. 24(5):554–561.Link, Google Scholar
• [25] Dexter F, Macario A, Traub RD (1999) Which algorithm for scheduling add-on elective cases maximizes operating room utilization? Use of bin packing algorithms and fuzzy constraints in operating room management. Anesthesiology 91(5):1491–1491.Crossref, Google Scholar
• [26] Fu H, Li J, Xu P (2018) A PTAS for a class of stochastic dynamic programs. Chatzigiannakis I, Kaklamanis C, Marx D, Sannella D, eds. Proc. 45th Internat. Colloquium on Automata, Languages, and Programming. (ICALP 2018), Prague, Czech Republic (Schloss Dagstuhl - Leibniz-Zentrum für Informatik), 107:56:1–56:14.Google Scholar
• [27] Garey MR, Graham RL, Johnson DS, Yao ACC (1976) Resource constrained scheduling as generalized bin packing. J. Combinatorial Theory Ser. A 21(3):257–298.Crossref, Google Scholar
• [28] Gilmore PC, Gomory RE (1961) A linear programming approach to the cutting-stock problem. Oper. Res. 9(6):849–859.Link, Google Scholar
• [29] Goel A, Indyk P (1999) Stochastic load balancing and related problems. Proc. 40th Annual Sympos. on Foundations of Comput. Sci. (IEEE, New York), 579–586.Google Scholar
• [30] Goyal V, Udwani R (2022) Online matching with stochastic rewards: Optimal competitive ratio via path based formulation. Oper. Res. Forthcoming.Google Scholar
• [31] Gupta V, Radovanovic A (2015) Lagrangian-based online stochastic bin packing. Performance Evaluation Rev. 43(1):467–468.Crossref, Google Scholar
• [32] Gupta V, Radovanović A (2020) Interior-point-based online stochastic bin packing. Oper. Res. 68(5):1474–1492.Link, Google Scholar
• [33] Gupta A, Krishnaswamy R, Molinaro M, Ravi R (2011) Approximation algorithms for correlated knapsacks and non-martingale bandits. Proc. IEEE 52nd Annual Sympos. on Foundations of Comput. Sci. (IEEE, New York), 827–836.Google Scholar
• [34] Hoberg R, Rothvoss T (2017) A logarithmic additive integrality gap for bin packing. Proc. 28th Annual ACM-SIAM Sympos. on Discrete Algorithms (SIAM, Philadelphia), 2616–2625.Google Scholar
• [35] Johnson DS (1974) Fast algorithms for bin packing. J. Comput. System Sci. 8(3):272–314.Crossref, Google Scholar
• [36] Karmarkar N, Karp RM (1982) An efficient approximation scheme for the one-dimensional bin-packing problem. Proc. 23rd Annual Sympos. on Foundations of Comput. Sci. (IEEE, New York), 312–320.Google Scholar
• [37] Kleinberg J, Rabani Y, Tardos É (2000) Allocating bandwidth for bursty connections. SIAM J. Comput. 30(1):191–217.Crossref, Google Scholar
• [38] Kleywegt A, Papastavrou J (1998) The dynamic and stochastic knapsack problem. Oper. Res. 46:17–35.Link, Google Scholar
• [39] Kleywegt A, Papastavrou J (2001) The dynamic and stochastic knapsack problem with random sized items. Oper. Res. 49:26–41.Link, Google Scholar
• [40] Levin A (2021) Approximation schemes for the generalized extensible bin packing problem. Algorithmica (Springer), 1–19.Google Scholar
• [41] Levin A, Vainer A (2014) Adaptivity in the stochastic blackjack knapsack problem. Theoretical Comput. Sci. 516:121–126.Crossref, Google Scholar
• [42] Li J, Yuan W (2013) Stochastic combinatorial optimization via poisson approximation. Proc. 45th Annual ACM Sympos. on Theory of Comput. (ACM, New York), 971–980.Google Scholar
• [43] Ma W (2018) Improvements and generalizations of stochastic knapsack and markovian bandits approximation algorithms. Math. Oper. Res. 43(3):789–812.Link, Google Scholar
• [44] Mehta A, Waggoner B, Zadimoghaddam M (2014) Online stochastic matching with unequal probabilities. Proc. 26th Annual ACM-SIAM Sympos. on Discrete Algorithms (SIAM, Philadelphia), 1388–1404.Google Scholar
• [45] Papastavrou J, Rajagopalan S, Kleywegt A (1996) The dynamic and stochastic knapsack problem with deadlines. Management Sci. 42:1706–1718.Link, Google Scholar
• [46] Powell WB (2007) Approximate Dynamic Programming: Solving the Curses of Dimensionality, vol. 703 (John Wiley & Sons, New York).Crossref, Google Scholar
• [47] Puterman ML (2014) Markov Decision Processes: Discrete Stochastic Dynamic Programming (John Wiley & Sons, New York).Google Scholar
• [48] Rhee WT (1988) Optimal bin packing with items of random sizes. Math. Oper. Res. 13(1):140–151.Link, Google Scholar
• [49] Ross SM (1996) Stochastic Processes, vol. 2 (Wiley, New York).Google Scholar
• [50] Rothvoß T (2013) Approximating bin packing within o(log opt* log log opt) bins. Proc. IEEE 54th Annual Sympos. on Foundations of Comput. Sci. (IEEE, New York), 20–29.Google Scholar
• [51] Sagnol G, Genannt Waldschmidt DS, Tesch A (2018) The price of fixed assignments in stochastic extensible bin packing. Proc. Internat. Workshop on Approximation and Online Algorithms (Springer, Berlin), 327–347.Google Scholar
• [52] Shor PW (1986) The average-case analysis of some on-line algorithms for bin packing. Combinatorica 6(2):179–200.Crossref, Google Scholar
• [53] Shor PW (1991) How to pack better than best fit: Tight bounds for average-case online bin packing. Proc. 32nd Annual Sympos. of Foundations of Comput. Sci. (IEEE, New York), 752–759.Google Scholar
• [54] Sipser M (1997) Introduction to the Theory of Computation (PWS Publishing Company, Boston).Google Scholar
• [55] Valiant LG (1979) The complexity of enumeration and reliability problems. SIAM J. Comput. 8(3):410–421.Crossref, Google Scholar
• [56] van Vliet A (1992) An improved lower bound for on-line bin packing algorithms. Inform. Processing Lett. 43(5):277–284.Crossref, Google Scholar
• [57] Vijayakumar B, Parikh PJ, Scott R, Barnes A, Gallimore J (2013) A dual bin-packing approach to scheduling surgical cases at a publicly funded hospital. Eur. J. Oper. Res. 224(3):583–591.Crossref, Google Scholar
• [58] Wilcox D, McNabb A, Seppi K (2011) Solving virtual machine packing with a reordering grouping genetic algorithm. Proc. IEEE Congress of Evolutionary Comput. (IEEE, New York), 362–369.Google Scholar
• [59] Wilson ID, Roach PA (1999) Principles of combinatorial optimization applied to container-ship stowage planning. J. Heuristics 5(4):403–418.Crossref, Google Scholar
• [60] Yao ACC (1980) New algorithms for bin packing. J. ACM 27(2):207–227.Crossref, Google Scholar