Submodular Stochastic Probing on Matroids
From MaRDI portal
Publication:3186541
DOI10.1287/moor.2015.0766zbMath1342.90112arXiv1310.4415MaRDI QIDQ3186541
Marek Adamczyk, M. I. Sviridenko, Justin Ward
Publication date: 10 August 2016
Published in: Mathematics of Operations Research (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1310.4415
stochastic optimization; matroids; iterative rounding; submodular maximization; sequential posted pricing; stochastic matching
Related Items
Unnamed Item, Unnamed Item, Submodular Maximization with Uncertain Knapsack Capacity, Stochastic submodular probing with state-dependent costs, Stochastic submodular probing with state-dependent costs, Query minimization under stochastic uncertainty, Online Contention Resolution Schemes with Applications to Bayesian Selection Problems, Constrained stochastic submodular maximization with state-dependent costs, Robust budget allocation via continuous submodular functions, Stochastic packing integer programs with few queries, An adversarial model for scheduling with testing, Price of dependence: stochastic submodular maximization with dependent items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- When LP is the cure for your matching woes: improved bounds for stochastic matchings
- Testing membership in matroid polyhedra
- On the Lambert \(w\) function
- Pipage rounding: a new method of constructing algorithms with proven performance guarantee
- Improved analysis of the greedy algorithm for stochastic matching
- On the complexity of approximating \(k\)-set packing
- Linear Programming under Uncertainty
- Multi-parameter mechanism design and sequential posted pricing
- Matroid matching
- Price of Correlations in Stochastic Optimization
- A threshold of ln n for approximating set cover
- Approximating the Stochastic Knapsack Problem: The Benefit of Adaptivity
- Maximizing a Monotone Submodular Function Subject to a Matroid Constraint
- Stochastic Covering and Adaptivity
- Approximating Matches Made in Heaven
- An analysis of approximations for maximizing submodular set functions—I
- Best Algorithms for Approximating the Maximum of a Submodular Set Function
- A Stochastic Probing Problem with Applications
- Matroid prophet inequalities
- Submodular function maximization via the multilinear relaxation and contention resolution schemes
- Maximizing a Submodular Set Function Subject to a Matroid Constraint (Extended Abstract)
- A Unified Continuous Greedy Algorithm for Submodular Maximization
- Approximation Algorithms for Correlated Knapsacks and Non-martingale Bandits
- Submodular Maximization over Multiple Matroids via Generalized Exchange Properties
