License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2020.13
URN: urn:nbn:de:0030-drops-124207
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12420/
Go to the corresponding LIPIcs Volume Portal

Bienkowski, Marcin ; Pacut, Maciej ; Piecuch, Krzysztof

An Optimal Algorithm for Online Multiple Knapsack

pdf-format:
LIPIcs-ICALP-2020-13.pdf (0.7 MB)

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
Collection: 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