A survey of online knapsack problems

Discrete Applied Mathematics, vol. 378, pp. 492–507

Abstract

We survey the current state of research on the knapsack problem in online and semi-online environments. In particular, we summarize what is known about models where different assumptions commonly made in online computation are relaxed: namely that online algorithms do not know the complete instances they are processing; have to make decisions that are irrevocable; and deal with an input chosen by a malicious adversary.

Authors 5

1. Hans-Joachim Böckenhauer

   ETH Zurich

   Affiliation as printed

   ETH Zurich, Department of Computer Science, Universitätstrasse 6, 8092, Zürich, Switzerland

2. Juraj Hromkovic̆

   ETH Zurich

   Affiliation as printed

   ETH Zurich, Department of Computer Science, Universitätstrasse 6, 8092, Zürich, Switzerland

3. Dennis Komm

   ETH Zurich

   Affiliation as printed

   ETH Zurich, Department of Computer Science, Universitätstrasse 6, 8092, Zürich, Switzerland

4. Peter Rossmanith Aachen Department of Computer Science

   RWTH Aachen University

   Affiliation as printed

   RWTH Aachen University, Department of Computer Science, Ahornstrasse 55, 52056, Aachen, Germany

5. Moritz Stocker corresponding

   ETH Zurich

   Affiliation as printed

   ETH Zurich, Department of Computer Science, Universitätstrasse 6, 8092, Zürich, Switzerland