Price of dependence: stochastic submodular maximization with dependent items

DOI10.1007/s10878-019-00470-6zbMath1437.90117arXiv1905.09719OpenAlexW2982703496MaRDI QIDQ2292144

Shaojie Tang

Publication date: 3 February 2020

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

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

zbMATH Keywords

stochastic optimizationapproximate algorithmsdependent variablessubmodular maximization

Mathematics Subject Classification ID

Stochastic programming (90C15) Approximation algorithms (68W25) Randomized algorithms (68W20)

Related Items (4)

Beyond pointwise submodularity: non-monotone adaptive submodular maximization in linear time ⋮ Adaptive robust submodular optimization and beyond ⋮ Beyond pointwise submodularity: non-monotone adaptive submodular maximization subject to knapsack and \(k\)-system constraints ⋮ Partial-monotone adaptive submodular maximization

Cites Work

• Unnamed Item
• Unnamed Item
• Pipage rounding: a new method of constructing algorithms with proven performance guarantee
• Discrete Stochastic Submodular Maximization: Adaptive vs. Non-adaptive vs. Offline
• Submodular Stochastic Probing on Matroids
• Maximizing a Monotone Submodular Function Subject to a Matroid Constraint
• Adaptivity Gaps for Stochastic Probing: Submodular and XOS Functions
• Submodular Function Maximization via the Multilinear Relaxation and Contention Resolution Schemes

This page was built for publication: Price of dependence: stochastic submodular maximization with dependent items