Sampling and Cost-Sharing: Approximation Algorithms for Stochastic Optimization Problems

DOI10.1137/080732250zbMath1252.68352OpenAlexW2008298964MaRDI QIDQ3115871

Anupam Gupta, Martin Pál, R. Ravi, Amitabh Sinha

Publication date: 11 February 2012

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/ad980334802933115adc54394a0f9bccc897870e

zbMATH Keywords

stochastic optimizationcombinatorial optimizationapproximation algorithmscost-sharing functions

Mathematics Subject Classification ID

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

Related Items (9)

Approximation algorithms for stochastic combinatorial optimization problems ⋮ Two-stage stochastic max-weight independent set problems ⋮ Approximation algorithm with constant ratio for stochastic prize-collecting Steiner tree problem ⋮ Thresholded covering algorithms for robust and max-min optimization ⋮ Configuration balancing for stochastic requests ⋮ Approximation Algorithms for Stochastic and Risk-Averse Optimization ⋮ Minimizing worst-case and average-case makespan over scenarios ⋮ The A priori traveling repairman problem ⋮ Approximation algorithm for stochastic set cover problem

This page was built for publication: Sampling and Cost-Sharing: Approximation Algorithms for Stochastic Optimization Problems