Submodular Stochastic Probing on Matroids

DOI10.1287/moor.2015.0766zbMath1342.90112arXiv1310.4415OpenAlexW2152854599MaRDI 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

zbMATH Keywords

stochastic optimizationmatroidsiterative roundingsubmodular maximizationsequential posted pricingstochastic matching

Mathematics Subject Classification ID

Stochastic programming (90C15) Combinatorial optimization (90C27) Approximation algorithms (68W25)

Related Items (12)

Stochastic packing integer programs with few queries ⋮ Constrained stochastic submodular maximization with state-dependent costs ⋮ Unnamed Item ⋮ An adversarial model for scheduling with testing ⋮ Robust budget allocation via continuous submodular functions ⋮ Price of dependence: stochastic submodular maximization with dependent items ⋮ Stochastic submodular probing with state-dependent costs ⋮ Stochastic submodular probing with state-dependent costs ⋮ Query minimization under stochastic uncertainty ⋮ Submodular Maximization with Uncertain Knapsack Capacity ⋮ Unnamed Item ⋮ Online Contention Resolution Schemes with Applications to Bayesian Selection Problems

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

This page was built for publication: Submodular Stochastic Probing on Matroids