Approximating the stochastic knapsack problem: the benefit of adaptivity

By B. C. Dean, Michel X. Goemans, Jan Vondr'ak. 45th Annual IEEE Symposium on Foundations of Computer Science, 2004

400 citations recorded by the source corpus.

Subfields: Computer Networks and Communications, Industrial and Manufacturing Engineering

View Paper: https://www.semanticscholar.org/paper/2aa3af7ec408ce237c64de78dd55a22fbc9e3041

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Networks and Communications

1. Andreas Krause
2. Robert D. Kleinberg
3. D. Golovin
4. Dimitris J. Bertsimas
5. Nicole Immorlica
6. Constantine Caramanis
7. David Kempe
8. Aleksandrs Slivkins

In Industrial and Manufacturing Engineering

1. Andreas Krause
2. D. Golovin
3. Dimitris J. Bertsimas

Citations in the corpus

• Theory and Applications of Robust Optimization (2010, background): “The papers by Dean, Goemans, and Vondrák (see [63, 82]) consider the value of adaptability in the context of stochastic optimization problems.”
• Adaptive Submodularity: Theory and Applications in Active Learning and Stochastic Optimization (2010, background): “Many approaches consider stochastic generalizations of specific classic non-adaptive optimization problems, such as Set Cover (Goemans and Vondrák, 2006; Liu et al., 2008), Knapsack (Dean et al., 2008, 2005) and Traveling Salesman (Gupta et al., 2010).”
• A Knapsack Secretary Problem with Applications (2007, background): “Dean et al. [7, 8] consider a stochastic offline knapsack problem where the algo-rithm knows the values and the distribution of the weights of the elements.”