Sampling and cost-sharing: approximation algorithms for stochastic optimization problems

DOI10.1137/080732250MaRDI QIDQ3115871zbMATH OpenOpenAlexFDO

Authors 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

approximation algorithmscombinatorial optimizationcost-sharing functionsstochastic optimization

Mathematics Subject Classification ID

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

Recommendations

• Boosted sampling
• Sampling-based approximation algorithms for multistage stochastic optimization
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Hedging uncertainty: approximation algorithms for stochastic optimization problems
• scientific article; zbMATH DE number 6381764

Cited in

(23)

• Minimizing worst-case and average-case makespan over scenarios
• Approximation algorithm for stochastic set cover problem
• Approximation algorithms for stochastic set cover and single sink rent-or-buy with submodular penalty
• Two-stage stochastic max-weight independent set problems
• Approximation algorithm with constant ratio for stochastic prize-collecting Steiner tree problem
• Approximation algorithm for the 2-stage stochastic matroid base problem
• Approximation algorithms for stochastic combinatorial optimization problems
• Network design for information networks
• Sampling and Representation Complexity of Revenue Maximization
• Sampling-based approximation algorithms for multistage stochastic optimization
• Sampling subproblems of heterogeneous Max-Cut problems and approximation algorithms
• Boosted sampling
• Thresholded covering algorithms for robust and max-min optimization
• Optimal sample cost residues for differential database batch query problems
• Approximation algorithms for stochastic and risk-averse optimization
• The price of information in combinatorial optimization
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Configuration balancing for stochastic requests
• Towards distributed two-stage stochastic optimization
• An o( n)-approximation for submodular facility location
• Configuration balancing for stochastic requests
• The A priori traveling repairman problem

This page was built for publication: Sampling and cost-sharing: approximation algorithms for stochastic optimization problems

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