Discrete Stochastic Submodular Maximization: Adaptive vs. Non-adaptive vs. Offline

DOI10.1007/978-3-319-18173-8_17zbMath1459.90136arXiv1504.02146OpenAlexW2963219439MaRDI QIDQ2947023

Patrick Lin, Devorah Kletenik, Lisa Hellerstein

Publication date: 21 September 2015

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1504.02146

Mathematics Subject Classification ID

Stochastic programming (90C15) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)

Related Items

Unnamed Item, Adaptivity gaps for the stochastic Boolean function evaluation problem, Price of dependence: stochastic submodular maximization with dependent items

Cites Work

• Unnamed Item
• Unnamed Item
• A note on maximizing a submodular set function subject to a knapsack constraint
• The budgeted maximum coverage problem
• Pipage rounding: a new method of constructing algorithms with proven performance guarantee
• A threshold of ln n for approximating set cover
• Stochastic Depletion Problems: Effective Myopic Policies for a Class of Dynamic Optimization Problems
• Maximising Real-Valued Submodular Functions: Primal and Dual Heuristics for Location Problems
• An analysis of approximations for maximizing submodular set functions—I
• Best Algorithms for Approximating the Maximum of a Submodular Set Function