(Near) Optimal Adaptivity Gaps for Stochastic Multi-Value Probing

Domagoj Bradač, Sahil Singla, Goran Žužić

Type: Preprint

Publication Date: 2019-02-04

Citations: 9

Locations

arXiv (Cornell University) - View

Similar Works

Action	Title	Year	Authors
+	(Near) Optimal Adaptivity Gaps for Stochastic Multi-Value Probing	2019	Domagoj Bradač Sahil Singla Goran Žužić
+	A Stochastic Probing Problem with Applications	2013	Anupam Gupta Viswanath Nagarajan
+	A Stochastic Probing Problem with Applications	2013	Anupam Gupta Viswanath Nagarajan
+	Ignorance is Almost Bliss: Near-Optimal Stochastic Matching With Few Queries	2014	Avrim Blum John P. Dickerson Nika Haghtalab Ariel D. Procaccia Tüomas Sandholm Ankit Sharma
+ PDF Chat	Ignorance is Almost Bliss: Near-Optimal Stochastic Matching With Few Queries	2015	Avrim Blum John P. Dickerson Nika Haghtalab Ariel D. Procaccia Tüomas Sandholm Ankit Sharma
+	Random Order Contention Resolution Schemes	2018	Marek Adamczyk Michał Włodarczyk
+	Random Order Contention Resolution Schemes	2018	Marek Adamczyk Michał Włodarczyk
+	Improved Approximation Algorithms for Stochastic-Matching Problems	2020	Marek Adamczyk Brian Brubach Fabrizio Grandoni Karthik Abinav Sankararaman Aravind Srinivasan Pan Xu
+ PDF Chat	Random Order Contention Resolution Schemes	2018	Marek Adamczyk Michał Włodarczyk
+ PDF Chat	Ignorance is Almost Bliss	2015	Avrim Blum John P. Dickerson Nika Haghtalab Ariel D. Procaccia Tüomas Sandholm Ankit Sharma
+ PDF Chat	Ignorance Is Almost Bliss: Near-Optimal Stochastic Matching with Few Queries	2020	Avrim Blum John P. Dickerson Nika Haghtalab Ariel D. Procaccia Tüomas Sandholm Ankit Sharma
+ PDF Chat	Submodular Stochastic Probing on Matroids	2016	Marek Adamczyk Maxim Sviridenko Justin Ward
+	Adaptivity Gaps for Stochastic Probing: Submodular and XOS Functions	2016	Anupam Gupta Viswanath Nagarajan Sahil Singla
+	Submodular Stochastic Probing with Prices	2018	Ben Chugg Takanori Maehara
+	Adaptivity Gaps for Stochastic Probing: Submodular and XOS Functions	2017	Anupam Gupta Viswanath Nagarajan Sahil Singla
+	Adaptivity gaps for stochastic probing: submodular and XOS functions	2017	Anupam Gupta Viswanath Nagarajan Sahil Singla
+	Almost Optimal Stochastic Weighted Matching With Few Queries	2017	Soheil Behnezhad Nima Reyhani
+	The Stochastic Matching Problem: Beating Half with a Non-Adaptive Algorithm	2017	Sepehr Assadi Sanjeev Khanna Yang Li
+	Non-negative submodular stochastic probing via stochastic contention resolution schemes	2015	Marek Adamczyk
+ PDF Chat	Almost Optimal Stochastic Weighted Matching with Few Queries	2018	Soheil Behnezhad Nima Reyhani

Works That Cite This (8)

Action	Title	Year	Authors
+	Adaptive Influence Maximization with Myopic Feedback	2019	Binghui Peng Wei Chen
+	On Adaptivity Gaps of Influence Maximization under the Independent Cascade Model with Full Adoption Feedback	2019	Wei Chen Binghui Peng
+ PDF Chat	Price of dependence: stochastic submodular maximization with dependent items	2019	Shaojie Tang
+	Improved Approximation Factor for Adaptive Influence Maximization via Simple Greedy Strategies	2020	Gianlorenzo D’Angelo Debashmita Poddar Cosimo Vinci
+	Delegated Stochastic Probing	2020	Curtis Bechtel Shaddin Dughmi
+	Probing to Minimize.	2021	Weina Wang Anupam Gupta Jalani K. Williams
+	Adaptive Robust Optimization with Nearly Submodular Structure	2019	Shaojie Tang Jing Yuan
+	Prophet Inequality Matching Meets Probing with Commitment.	2021	Allan Borodin Calum MacRury Akash Rakheja

Works Cited by This (11)

Action	Title	Year	Authors
+ PDF Chat	Improved Approximation Algorithms for Stochastic Matching	2015	Marek Adamczyk Fabrizio Grandoni Joydeep Mukherjee
+ PDF Chat	When LP Is the Cure for Your Matching Woes: Improved Bounds for Stochastic Matchings	2011	Nikhil Bansal Anupam Gupta Jian Li Julián Mestre Viswanath Nagarajan Atri Rudra
+ PDF Chat	Approximation Algorithms for Correlated Knapsacks and Non-martingale Bandits	2011	Anupam Gupta Ravishankar Krishnaswamy Marco Molinaro R. Ravi
+ PDF Chat	Stochastic combinatorial optimization via poisson approximation	2013	Jian Li Wen Yuan
+ PDF Chat	Submodular Function Maximization via the Multilinear Relaxation and Contention Resolution Schemes	2014	Chandra Chekuri J. Vondrák Rico Zenklusen
+ PDF Chat	A Stochastic Probing Problem with Applications	2013	Anupam Gupta Viswanath Nagarajan
+	Adaptivity gaps for stochastic probing: submodular and XOS functions	2017	Anupam Gupta Viswanath Nagarajan Sahil Singla
+ PDF Chat	On the Adaptivity Gap of Stochastic Orienteering	2014	Nikhil Bansal Viswanath Nagarajan
+ PDF Chat	Maximizing Stochastic Monotone Submodular Functions	2015	Arash Asadpour Hamid Nazerzadeh
+ PDF Chat	Discrete Stochastic Submodular Maximization: Adaptive vs. Non-adaptive vs. Offline	2015	Lisa Hellerstein Devorah Kletenik Patrick Lin