A Stochastic Probing Problem with Applications

DOI10.1007/978-3-642-36694-9_18zbMath1372.90091arXiv1302.5913OpenAlexW2149744080MaRDI QIDQ4910817

Viswanath Nagarajan, Anupam Gupta

Publication date: 19 March 2013

Published in: Integer Programming and Combinatorial Optimization (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Stochastic programming (90C15) Combinatorial optimization (90C27) Auctions, bargaining, bidding and selling, and other market models (91B26)

Related Items (22)

Approximation algorithms for stochastic combinatorial optimization problems ⋮ Submodular Stochastic Probing on Matroids ⋮ Non-adaptive stochastic score classification and explainable halfspace evaluation ⋮ Stochastic packing integer programs with few queries ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Stochastic graph exploration with limited resources ⋮ Stochastic Probing with Increasing Precision ⋮ Unnamed Item ⋮ Unnamed Item ⋮ An adversarial model for scheduling with testing ⋮ Ignorance Is Almost Bliss: Near-Optimal Stochastic Matching with Few Queries ⋮ On the intersection of independence systems ⋮ Attenuate locally, win globally: attenuation-based frameworks for online stochastic matching with timeouts ⋮ Query minimization under stochastic uncertainty ⋮ Guess free maximization of submodular and linear sums ⋮ Stochastic graph exploration ⋮ Unnamed Item ⋮ Algorithms for the unit-cost stochastic score classification problem ⋮ Online Allocation and Pricing: Constant Regret via Bellman Inequalities ⋮ Online Contention Resolution Schemes with Applications to Bayesian Selection Problems ⋮ An optimal monotone contention resolution scheme for bipartite matchings via a polyhedral viewpoint

This page was built for publication: A Stochastic Probing Problem with Applications