Stochastic Probing with Increasing Precision

DOI10.1137/22m149466xOpenAlexW4390668818MaRDI QIDQ6187078

Kevin Schewior, Martin Hoefer, Daniel Schmand

Publication date: 10 January 2024

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/22m149466x

zbMATH Keywords

optimal stoppingtestingstochastic probing

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Learning and adaptive systems in artificial intelligence (68T05) Approximation algorithms (68W25) Optimal stopping in statistics (62L15)

Cites Work

• When LP is the cure for your matching woes: improved bounds for stochastic matchings
• The Markovian price of information
• Multi-parameter mechanism design and sequential posted pricing
• Submodular Stochastic Probing on Matroids
• Approximating the Stochastic Knapsack Problem: The Benefit of Adaptivity
• How to probe for an extreme value
• Approximating Matches Made in Heaven
• Optimal Search for the Best Alternative
• Semiamarts and finite values
• Algorithms and Adaptivity Gaps for Stochastic Probing
• Adaptivity Gaps for Stochastic Probing: Submodular and XOS Functions
• A Stochastic Probing Problem with Applications
• Improvements and Generalizations of Stochastic Knapsack and Markovian Bandits Approximation Algorithms
• Bayesian Combinatorial Auctions: Expanding Single Buyer Mechanisms to Many Buyers
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Stochastic Probing with Increasing Precision