The online knapsack problem with incremental capacity

Clemens Thielen, Morten Tiedemann, Stephan Westphal

Research output: Contribution to journalArticlepeer-review

11 Scopus citations

Abstract

We consider an online knapsack problem with incremental capacity. In each time period, a set of items, each with a specific weight and value, is revealed and, without knowledge of future items, it has to be decided which of these items to accept. Additionally, the knapsack capacity is not fully available from the start but increases by a constant amount in each time period. The goal is to maximize the overall value of the accepted items. This setting extends the basic online knapsack problem by introducing a dynamic instead of a static knapsack capacity and is applicable to classic problems such as resource allocation or one-way trading. In contrast to the basic online knapsack problem, for which no competitive algorithms exist, the setting of incremental capacity facilitates the development of competitive algorithms for a bounded time horizon. We provide a competitive analysis of deterministic and randomized online algorithms for the online knapsack problem with incremental capacity and present lower bounds on the competitive ratio achievable by online algorithms for the problem. Most of these lower bounds match the competitive ratios achieved by our online algorithms exactly or differ only by a constant factor.

Original languageEnglish
Pages (from-to)207-242
Number of pages36
JournalMathematical Methods of Operations Research
Volume83
Issue number2
DOIs
StatePublished - 1 Apr 2016
Externally publishedYes

Keywords

  • Competitive analysis
  • Dynamic capacity
  • Knapsack problems
  • Online optimization

Fingerprint

Dive into the research topics of 'The online knapsack problem with incremental capacity'. Together they form a unique fingerprint.

Cite this