Identifying approximate minimizers under stochastic uncertainity

DOI10.4230/LIPICS.ICALP.2025.8MaRDI QIDQ7346435zbMATH OpenFDO

Authors Hessa Al-Thani, Viswanath Nagarajan

Publication date 10 September 2026

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.ICALP.2025.8

Mathematics Subject Classification ID

Theory of software (68Nxx) Theory of computing (68Qxx)

Cites work

• A PTAS for a class of stochastic dynamic programs
• A Tight Bound for Stochastic Submodular Cover
• Adaptivity gaps for stochastic probing: submodular and XOS functions
• Approximating the stochastic Knapsack problem: the benefit of adaptivity
• Approximation algorithms for budgeted learning problems
• Computing minimum spanning trees with uncertainty
• Computing the median with uncertainty
• How to probe for an extreme value
• scientific article; zbMATH DE number 7650393 (Why is no real title available?)
• scientific article; zbMATH DE number 7740865 (Why is no real title available?)
• scientific article; zbMATH DE number 7829352 (Why is no real title available?)
• Minimum latency submodular cover
• Query minimization under stochastic uncertainty
• Query-competitive algorithms for cheapest set problems under uncertainty
• Quickly determining who won an election
• Randomization Helps Computing a Minimum Spanning Tree under Uncertainty
• Running Errands in Time: Approximation Algorithms for Stochastic Orienteering
• Set selection under explorable stochastic uncertainty via covering techniques
• Submodular stochastic probing on matroids
• The price of information in combinatorial optimization
• The stochastic score classification problem
• When LP is the cure for your matching woes: improved bounds for stochastic matchings

This page was built for publication: Identifying approximate minimizers under stochastic uncertainity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7346435)