The online knapsack problem with incremental capacity
2016 | journal article. A publication with affiliation to the University of Göttingen.
Jump to: Cite & Linked | Documents & Media | Details | Version history
Documents & Media
Details
- Authors
- Thielen, Clemens; Tiedemann, Morten; Westphal, Stephan
- 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.
- Issue Date
- 2016
- Status
- published
- Publisher
- Springer
- Journal
- Mathematical Methods of Operations Research
- ISSN
- 1432-5217; 1432-2994
- Sponsor
- German Research Foundation (DFG) [GRK 1703/1]