Algorithms and Adaptivity Gaps for Stochastic Probing

DOI10.1137/1.9781611974331.ch120zbMath1415.90102OpenAlexW4245298853MaRDI QIDQ4575704

Sahil Singla, Anupam Gupta, Viswanath Nagarajan

Publication date: 16 July 2018

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

Full work available at URL: https://doi.org/10.1137/1.9781611974331.ch120

Mathematics Subject Classification ID

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

Related Items (11)

Better bounds on the adaptivity gap of influence maximization under full-adoption feedback ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Stochastic graph exploration with limited resources ⋮ Adaptivity gaps for the stochastic Boolean function evaluation problem ⋮ Stochastic Probing with Increasing Precision ⋮ Unnamed Item ⋮ An adversarial model for scheduling with testing ⋮ Query minimization under stochastic uncertainty ⋮ Stochastic graph exploration ⋮ Online Allocation and Pricing: Constant Regret via Bellman Inequalities

This page was built for publication: Algorithms and Adaptivity Gaps for Stochastic Probing