Adaptivity Gaps for Stochastic Probing: Submodular and XOS Functions

DOI10.1137/1.9781611974782.111zbMath1423.90159arXiv1608.00673OpenAlexW2950535090MaRDI QIDQ4575854

Viswanath Nagarajan, Anupam Gupta, Sahil Singla

Publication date: 16 July 2018

Published in: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Stochastic programming (90C15) Combinatorial optimization (90C27)

Related Items (14)

Non-adaptive stochastic score classification and explainable halfspace evaluation ⋮ Fast Adaptive Non-Monotone Submodular Maximization Subject to a Knapsack Constraint ⋮ Stochastic packing integer programs with few queries ⋮ Better bounds on the adaptivity gap of influence maximization under full-adoption feedback ⋮ Unnamed Item ⋮ Adaptivity gaps for the stochastic Boolean function evaluation problem ⋮ Stochastic Probing with Increasing Precision ⋮ Adaptive robust submodular optimization and beyond ⋮ Price of dependence: stochastic submodular maximization with dependent items ⋮ Query minimization under stochastic uncertainty ⋮ Submodular Maximization with Uncertain Knapsack Capacity ⋮ Unnamed Item ⋮ Budget-Feasible Mechanism Design for Non-monotone Submodular Objectives: Offline and Online ⋮ Scheduling with a processing time oracle

This page was built for publication: Adaptivity Gaps for Stochastic Probing: Submodular and XOS Functions