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.APPROX-RANDOM.2019.22
URN: urn:nbn:de:0030-drops-112376
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/11237/
Go to the corresponding LIPIcs Volume Portal

Albers, Susanne ; Khan, Arindam ; Ladewig, Leon

Improved Online Algorithms for Knapsack and GAP in the Random Order Model

pdf-format:
LIPIcs-APPROX-RANDOM-2019-22.pdf (0.6 MB)

Abstract

The knapsack problem is one of the classical problems in combinatorial optimization: Given a set of items, each specified by its size and profit, the goal is to find a maximum profit packing into a knapsack of bounded capacity. In the online setting, items are revealed one by one and the decision, if the current item is packed or discarded forever, must be done immediately and irrevocably upon arrival. We study the online variant in the random order model where the input sequence is a uniform random permutation of the item set.
We develop a randomized (1/6.65)-competitive algorithm for this problem, outperforming the current best algorithm of competitive ratio 1/8.06 [Kesselheim et al. SIAM J. Comp. 47(5)]. Our algorithm is based on two new insights: We introduce a novel algorithmic approach that employs two given algorithms, optimized for restricted item classes, sequentially on the input sequence. In addition, we study and exploit the relationship of the knapsack problem to the 2-secretary problem.
The generalized assignment problem (GAP) includes, besides the knapsack problem, several important problems related to scheduling and matching. We show that in the same online setting, applying the proposed sequential approach yields a (1/6.99)-competitive randomized algorithm for GAP. Again, our proposed algorithm outperforms the current best result of competitive ratio 1/8.06 [Kesselheim et al. SIAM J. Comp. 47(5)].

BibTeX - Entry

@InProceedings{albers_et_al:LIPIcs:2019:11237,
  author =	{Susanne Albers and Arindam Khan and Leon Ladewig},
  title =	{{Improved Online Algorithms for Knapsack and GAP in the Random Order Model}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
  pages =	{22:1--22:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-125-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{145},
  editor =	{Dimitris Achlioptas and L{\'a}szl{\'o} A. V{\'e}gh},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2019/11237},
  URN =		{urn:nbn:de:0030-drops-112376},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2019.22},
  annote =	{Keywords: Online algorithms, knapsack problem, random order model}
}

Keywords: Online algorithms, knapsack problem, random order model
Collection: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)
Issue Date: 2019
Date of publication: 17.09.2019

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