Lower bounds on the adaptivity gaps in variants of the stochastic knapsack problem

Asaf Levin () and Aleksander Vainer ()
Additional contact information
Asaf Levin: The Technion
Aleksander Vainer: The Technion

Journal of Combinatorial Optimization, 2018, vol. 35, issue 3, No 8, 794-813

Abstract: Abstract We consider stochastic variants of the NP-hard 0/1 knapsack problem in which item values are deterministic and item sizes are independent random variables with known, arbitrary distributions. Items are placed in the knapsack sequentially, and the act of placing an item in the knapsack instantiates its size. The goal is to compute a policy for insertion of the items, that maximizes the expected value of the set of items placed in the knapsack. These variants that we study differ only in the formula for computing the value of the final solution obtained by the policy. We consider both nonadaptive policies (that designate a priori a fixed subset or permutation of items to insert) and adaptive policies (that can make dynamic decisions based on the instantiated sizes of the items placed in the knapsack thus far). Our work characterizes the benefit of adaptivity. For this purpose we use a measure called the adaptivity gap: the supremum over instances of the ratio between the expected value obtained by an optimal adaptive policy and the expected value obtained by an optimal non-adaptive policy. We show that while for the variants considered in the literature this quantity is bounded by a constant there are other variants where it is unbounded.

Keywords: Knapsack; Benefit of adaptivity; Stochastic combinatorial optimization (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-017-0234-x Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:35:y:2018:i:3:d:10.1007_s10878-017-0234-x

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-017-0234-x

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().