Near-Optimal Algorithms for Stochastic Online Bin Packing

Authors Nikhil ^* Ayyadevara, Rajni Dabas , Arindam Khan , K. V. N. Sreenivas



PDF
Thumbnail PDF

File

LIPIcs.ICALP.2022.12.pdf
  • Filesize: 0.87 MB
  • 20 pages

Document Identifiers

Author Details

Nikhil ^* Ayyadevara
  • Indian Institute of Technology Delhi, India
Rajni Dabas
  • Department of Computer Science, University of Delhi, India
Arindam Khan
  • Department of Computer Science and Automation, Indian Institute of Science, Bengaluru, India
K. V. N. Sreenivas
  • Department of Computer Science and Automation, Indian Institute of Science, Bengaluru, India

Acknowledgements

We thank Susanne Albers, Leon Ladewig, and Jirí Sgall for helpful initial discussions. We also thank three anonymous reviewers for their comments and suggestions.

Cite AsGet BibTex

Nikhil ^* Ayyadevara, Rajni Dabas, Arindam Khan, and K. V. N. Sreenivas. Near-Optimal Algorithms for Stochastic Online Bin Packing. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 12:1-12:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.ICALP.2022.12

Abstract

We study the online bin packing problem under two stochastic settings. In the bin packing problem, we are given n items with sizes in (0,1] and the goal is to pack them into the minimum number of unit-sized bins. First, we study bin packing under the i.i.d. model, where item sizes are sampled independently and identically from a distribution in (0,1]. Both the distribution and the total number of items are unknown. The items arrive one by one and their sizes are revealed upon their arrival and they must be packed immediately and irrevocably in bins of size 1. We provide a simple meta-algorithm that takes an offline α-asymptotic proximation algorithm and provides a polynomial-time (α + ε)-competitive algorithm for online bin packing under the i.i.d. model, where ε > 0 is a small constant. Using the AFPTAS for offline bin packing, we thus provide a linear time (1+ε)-competitive algorithm for online bin packing under i.i.d. model, thus settling the problem. We then study the random-order model, where an adversary specifies the items, but the order of arrival of items is drawn uniformly at random from the set of all permutations of the items. Kenyon’s seminal result [SODA'96] showed that the Best-Fit algorithm has a competitive ratio of at most 3/2 in the random-order model, and conjectured the ratio to be ≈ 1.15. However, it has been a long-standing open problem to break the barrier of 3/2 even for special cases. Recently, Albers et al. [Algorithmica'21] showed an improvement to 5/4 competitive ratio in the special case when all the item sizes are greater than 1/3. For this special case, we settle the analysis by showing that Best-Fit has a competitive ratio of 1. We also make further progress by breaking the barrier of 3/2 for the 3-Partition problem, a notoriously hard special case of bin packing, where all item sizes lie in (1/4,1/2].

Subject Classification

ACM Subject Classification
  • Theory of computation → Online algorithms
Keywords
  • Bin Packing
  • 3-Partition Problem
  • Online Algorithms
  • Random Order Arrival
  • IID model
  • Best-Fit Algorithm

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Susanne Albers, Arindam Khan, and Leon Ladewig. Best fit bin packing with random order revisited. Algorithmica, 83(9):2833-2858, 2021. Google Scholar
  2. Susanne Albers, Arindam Khan, and Leon Ladewig. Improved online algorithms for knapsack and GAP in the random order model. Algorithmica, 83(6):1750-1785, 2021. Google Scholar
  3. Brenda S Baker and Edward G Coffman, Jr. A tight asymptotic bound for next-fit-decreasing bin-packing. SIAM Journal on Algebraic Discrete Methods, 2(2):147-152, 1981. Google Scholar
  4. János Balogh, József Békési, György Dósa, Leah Epstein, and Asaf Levin. A new and improved algorithm for online bin packing. In ESA, volume 112, pages 5:1-5:14, 2018. Google Scholar
  5. János Balogh, József Békési, György Dósa, Leah Epstein, and Asaf Levin. A new lower bound for classic online bin packing. In WAOA, volume 11926, pages 18-28. Springer, 2019. Google Scholar
  6. Nikhil Bansal, Marek Eliás, and Arindam Khan. Improved approximation for vector bin packing. In SODA, pages 1561-1579, 2016. Google Scholar
  7. Jozsef Bekesi, Gabor Galambos, and Hans Kellerer. A 5/4 linear time bin packing algorithm. Journal of Computer and System Sciences, 60(1):145-160, 2000. Google Scholar
  8. Jon Louis Bentley, David S Johnson, Frank Thomson Leighton, Catherine C McGeoch, and Lyle A McGeoch. Some unexpected expected behavior results for bin packing. In STOC, pages 279-288, 1984. Google Scholar
  9. Carsten Oliver Fischer. New Results on the Probabilistic Analysis of Online Bin Packing and its Variants. PhD thesis, Rheinische Friedrich-Wilhelms-Universität Bonn, December 2019. Google Scholar
  10. Edward G Coffman Jr, János Csirik, Gábor Galambos, Silvano Martello, and Daniele Vigo. Bin packing approximation algorithms: survey and classification. In Handbook of combinatorial optimization, pages 455-531. Springer New York, 2013. Google Scholar
  11. Edward G Coffman Jr, David S Johnson, George S Lueker, and Peter W Shor. Probabilistic analysis of packing and related partitioning problems. Statistical Science, 8(1):40-47, 1993. Google Scholar
  12. Edward G Coffman Jr, David S Johnson, Peter W Shor, and Richard R Weber. Bin packing with discrete item sizes, part ii: Tight bounds on first fit. Random Structures & Algorithms, 10(1-2):69-101, 1997. Google Scholar
  13. Edward G Coffman Jr, Kimming So, Micha Hofri, and AC Yao. A stochastic model of bin-packing. Information and Control, 44(2):105-115, 1980. Google Scholar
  14. Janos Csirik, David S Johnson, Claire Kenyon, James B Orlin, Peter W Shor, and Richard R Weber. On the sum-of-squares algorithm for bin packing. Journal of the ACM (JACM), 53(1):1-65, 2006. Google Scholar
  15. W Fernandez de la Vega and George S Lueker. Bin packing can be solved within 1+epsilon in linear time. Combinatorica, 1(4):349-355, 1981. Google Scholar
  16. Brian C Dean, Michel X Goemans, and Jan Vondrák. Approximating the stochastic knapsack problem: The benefit of adaptivity. Mathematics of Operations Research, 33(4):945-964, 2008. Google Scholar
  17. Friedrich Eisenbrand, Dömötör Pálvölgyi, and Thomas Rothvoß. Bin packing via discrepancy of permutations. In SODA, pages 476-481, 2011. Google Scholar
  18. Jon Feldman, Aranyak Mehta, Vahab Mirrokni, and Shan Muthukrishnan. Online stochastic matching: Beating 1-1/e. In FOCS, pages 117-126, 2009. Google Scholar
  19. Thomas S Ferguson. Who solved the secretary problem? Statistical science, 4(3):282-289, 1989. Google Scholar
  20. Carsten Fischer and Heiko Röglin. Probabilistic analysis of the dual next-fit algorithm for bin covering. In LATIN, pages 469-482, 2016. Google Scholar
  21. Carsten Fischer and Heiko Röglin. Probabilistic analysis of online (class-constrained) bin packing and bin covering. In LATIN, volume 10807, pages 461-474. Springer, 2018. Google Scholar
  22. Anupam Gupta, Ravishankar Krishnaswamy, and R Ravi. Online and stochastic survivable network design. SIAM Journal on Computing, 41(6):1649-1672, 2012. Google Scholar
  23. Anupam Gupta, Amit Kumar, Viswanath Nagarajan, and Xiangkun Shen. Stochastic load balancing on unrelated machines. Mathematics of Operations Research, 46(1):115-133, 2021. Google Scholar
  24. Anupam Gupta and Sahil Singla. Random-order models. In Beyond the Worst-Case Analysis of Algorithms, pages 234-258. Cambridge University Press, 2020. Google Scholar
  25. Rebecca Hoberg and Thomas Rothvoss. A logarithmic additive integrality gap for bin packing. In SODA, pages 2616-2625, 2017. Google Scholar
  26. David S Johnson. Near-optimal bin packing algorithms. PhD thesis, Massachusetts Institute of Technology, 1973. Google Scholar
  27. David S Johnson. Fast algorithms for bin packing. J. Comput. Syst. Sci., 8(3):272-314, 1974. Google Scholar
  28. David S Johnson, Alan Demers, Jeffrey D Ullman, Michael R Garey, and Ronald L. Graham. Worst-case performance bounds for simple one-dimensional packing algorithms. SIAM Journal on computing, 3(4):299-325, 1974. Google Scholar
  29. David S Johnson and Michael R Garey. A 71/60 theorem for bin packing. J. Complex., 1(1):65-106, 1985. Google Scholar
  30. Edward G Coffman Jr, János Csirik, Lajos Rónyai, and Ambrus Zsbán. Random-order bin packing. Discret. Appl. Math., 156(14):2810-2816, 2008. Google Scholar
  31. Narendra Karmarkar and Richard M Karp. An efficient approximation scheme for the one-dimensional bin-packing problem. In FOCS, pages 312-320, 1982. Google Scholar
  32. Claire Kenyon. Best-fit bin-packing with random order. In SODA, pages 359-364, 1996. Google Scholar
  33. Chan C Lee and Der-Tsai Lee. A simple on-line bin-packing algorithm. J. ACM, 32(3):562-572, July 1985. Google Scholar
  34. Chan C Lee and Der-Tsai Lee. Robust on-line bin packing algorithms. Technical Report, Northwestern University, 1987. Google Scholar
  35. Tom Leighton and Peter Shor. Tight bounds for minimax grid matching with applications to the average case analysis of algorithms. Combinatorica, 9(2):161-187, 1989. Google Scholar
  36. Mohammad Mahdian and Qiqi Yan. Online bipartite matching with random arrivals: an approach based on strongly factor-revealing lps. In STOC, pages 597-606, 2011. Google Scholar
  37. Frank D Murgolo. Anomalous behavior in bin packing algorithms. Discret. Appl. Math., 21(3):229-243, 1988. Google Scholar
  38. Alantha Newman, Ofer Neiman, and Aleksandar Nikolov. Beck’s three permutations conjecture: A counterexample and some consequences. In FOCS, pages 253-262, 2012. Google Scholar
  39. Prakash V Ramanan. Average-case analysis of the smart next fit algorithm. Inf. Process. Lett., 31(5):221-225, 1989. Google Scholar
  40. W. T. Rhee. Inequalities for bin packing-iii. Optimization, 29(4):381-385, 1994. URL: https://doi.org/10.1080/02331939408843965.
  41. Wansoo T Rhee and Michel Talagrand. Exact bounds for the stochastic upward matching problem. Transactions of the American Mathematical Society, 307(1):109-125, 1988. Google Scholar
  42. Wansoo T Rhee and Michel Talagrand. On-line bin packing of items of random sizes, ii. SIAM Journal on Computing, 22(6):1251-1256, 1993. Google Scholar
  43. Wansoo T Rhee and Michel Talagrand. On line bin packing with items of random size. Mathematics of Operations Research, 18(2):438-445, 1993. Google Scholar
  44. Peter W Shor. The average-case analysis of some on-line algorithms for bin packing. Combinatorica, 6(2):179-200, 1986. Google Scholar
  45. Joel Spencer. Ten lectures on the probabilistic method. SIAM, 1994. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail