Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH scholarly article en Bienkowski, Marcin; Pacut, Maciej; Piecuch, Krzysztof https://www.dagstuhl.de/lipics License: Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)
when quoting this document, please refer to the following
DOI:
URN: urn:nbn:de:0030-drops-124207
URL:

; ;

An Optimal Algorithm for Online Multiple Knapsack

pdf-format:


Abstract

In the online multiple knapsack problem, an algorithm faces a stream of items, and each item has to be either rejected or stored irrevocably in one of n bins (knapsacks) of equal size. The gain of an algorithm is equal to the sum of sizes of accepted items and the goal is to maximize the total gain. So far, for this natural problem, the best solution was the 0.5-competitive algorithm FirstFit (the result holds for any n ≥ 2). We present the first algorithm that beats this ratio, achieving the competitive ratio of 1/(1+ln(2))-O(1/n) ≈ 0.5906 - O(1/n). Our algorithm is deterministic and optimal up to lower-order terms, as the upper bound of 1/(1+ln(2)) for randomized solutions was given previously by Cygan et al. [TOCS 2016].

BibTeX - Entry

@InProceedings{bienkowski_et_al:LIPIcs:2020:12420,
  author =	{Marcin Bienkowski and Maciej Pacut and Krzysztof Piecuch},
  title =	{{An Optimal Algorithm for Online Multiple Knapsack}},
  booktitle =	{47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
  pages =	{13:1--13:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-138-2},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{168},
  editor =	{Artur Czumaj and Anuj Dawar and Emanuela Merelli},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/12420},
  URN =		{urn:nbn:de:0030-drops-124207},
  doi =		{10.4230/LIPIcs.ICALP.2020.13},
  annote =	{Keywords: online knapsack, multiple knapsacks, bin packing, competitive analysis}
}

Keywords: online knapsack, multiple knapsacks, bin packing, competitive analysis
Seminar: 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)
Issue date: 2020
Date of publication: 29.06.2020


DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI