1 Search Results for "Dabas, Rajni"

Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2022.12
Near-Optimal Algorithms for Stochastic Online Bin Packing

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

Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)

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].
Cite as

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)

Copy BibTex To Clipboard

@InProceedings{ayyadevara_et_al:LIPIcs.ICALP.2022.12,
  author =	{Ayyadevara, Nikhil ^* and Dabas, Rajni and Khan, Arindam and Sreenivas, K. V. N.},
  title =	{{Near-Optimal Algorithms for Stochastic Online Bin Packing}},
  booktitle =	{49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
  pages =	{12:1--12:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-235-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{229},
  editor =	{Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.12},
  URN =		{urn:nbn:de:0030-drops-163532},
  doi =		{10.4230/LIPIcs.ICALP.2022.12},
  annote =	{Keywords: Bin Packing, 3-Partition Problem, Online Algorithms, Random Order Arrival, IID model, Best-Fit Algorithm}
}
  • Refine by Author
  • 1 Ayyadevara, Nikhil ^*
  • 1 Dabas, Rajni
  • 1 Khan, Arindam
  • 1 Sreenivas, K. V. N.

  • Refine by Classification
  • 1 Theory of computation → Online algorithms

  • Refine by Keyword
  • 1 3-Partition Problem
  • 1 Best-Fit Algorithm
  • 1 Bin Packing
  • 1 IID model
  • 1 Online Algorithms
  • Show More...

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2022

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
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact