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

Lisa Hellerstein, Devorah Kletenik, Patrick Lin

Type: Book-Chapter

Publication Date: 2015-01-01

Citations: 5

DOI: https://doi.org/10.1007/978-3-319-18173-8_17

View Publication

Download PDF

Locations

Lecture notes in computer science - View
arXiv (Cornell University) - View - PDF

Similar Works

Action	Title	Year	Authors
+ PDF Chat	Streaming Adaptive Submodular Maximization	2022	Shaojie Tang Jing Yuan
+ PDF Chat	Streaming adaptive submodular maximization	2022	Shaojie Tang Jing Yuan
+ PDF Chat	Partial-Adaptive Submodular Maximization	2023	Shaojie Tang Jing Yuan
+ PDF Chat	Stochastic submodular probing with state-dependent costs	2022	Shaojie Tang
+ PDF Chat	Stochastic Submodular Probing with State-Dependent Costs	2021	Shaojie Tang
+ PDF Chat	Gradient-bounded dynamic programming for submodular and concave extensible value functions with probabilistic performance guarantees	2021	Denis Lebedev Paul J. Goulart Kostas Margellos
+	Black Box Submodular Maximization: Discrete and Continuous Settings	2019	Lin Chen Mingrui Zhang Hamed Hassani Amin Karbasi
+ PDF Chat	Streaming Algorithms for Submodular Function Maximization	2015	Chandra Chekuri Shalmoli Gupta Kent Quanrud
+ PDF Chat	Partial-monotone adaptive submodular maximization	2022	Shaojie Tang Jing Yuan
+	Black Box Submodular Maximization: Discrete and Continuous Settings.	2019	Lin Chen Mingrui Zhang Hamed Hassani Amin Karbasi
+	High Probability Bounds for Stochastic Continuous Submodular Maximization	2023	Evan Becker Jingdong Gao Ted Zadouri Baharan Mirzasoleiman
+	Discrete Stochastic Submodular Maximization: Adaptive vs. Non-Adaptive vs. Offline	2015	Lisa Hellerstein Devorah Kletenik Patrick Lin
+ PDF Chat	Online Submodular Maximization: Beating 1/2 Made Simple	2019	Niv Buchbinder Moran Feldman Yuval Filmus Mohit Garg
+ PDF Chat	Online submodular maximization: beating 1/2 made simple	2020	Niv Buchbinder Moran Feldman Yuval Filmus Mohit Garg
+ PDF Chat	Beyond pointwise submodularity: Non-monotone adaptive submodular maximization in linear time	2020	Shaojie Tang
+ PDF Chat	Constrained Stochastic Submodular Maximization with State-Dependent Costs	2022	Shaojie Tang
+	Adaptive Cascade Submodular Maximization.	2020	Shaojie Tang Jing Yuan
+	Adaptive Submodularity: Theory and Applications in Active Learning and Stochastic Optimization	2010	Daniel Golovin Andreas Krause
+	Adaptive Submodularity: A New Approach to Active Learning and Stochastic Optimization	2010	Daniel Golovin Andreas Krause
+ PDF Chat	Stochastic Submodular Maximization via Polynomial Estimators	2023	Gözde Özcan Stratis Ioannidis

Works That Cite This (5)

Action	Title	Year	Authors
+	(Near) Optimal Adaptivity Gaps for Stochastic Multi-Value Probing	2019	Domagoj Bradač Sahil Singla Goran Žužić
+ PDF Chat	Price of dependence: stochastic submodular maximization with dependent items	2019	Shaojie Tang
+ PDF Chat	Adaptivity Gaps for the Stochastic Boolean Function Evaluation Problem	2022	Lisa Hellerstein Devorah Kletenik Naifeng Liu R. Teal Witter
+ PDF Chat	Stochastic Submodular Cover with Limited Adaptivity	2019	Arpit Agarwal Sepehr Assadi Sanjeev Khanna
+	Improved Approximation Factor for Adaptive Influence Maximization via Simple Greedy Strategies	2020	Gianlorenzo D’Angelo Debashmita Poddar Cosimo Vinci

Works Cited by This (2)

Action	Title	Year	Authors
+ PDF Chat	Stochastic Depletion Problems: Effective Myopic Policies for a Class of Dynamic Optimization Problems	2009	Carri W. Chan Vivek F. Farias
+ PDF Chat	Maximizing Stochastic Monotone Submodular Functions	2015	Arash Asadpour Hamid Nazerzadeh