An approximation scheme for stochastic linear programming and its application to stochastic integer programs

DOI10.1145/1217856.1217860zbMath1326.90059OpenAlexW2057974767MaRDI QIDQ3455224

Publication date: 4 December 2015

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1217856.1217860

zbMATH Keywords

convex optimization facility location approximation algorithms randomized algorithms vertex cover multicommodity flow set cover

Mathematics Subject Classification ID

Integer programming (90C10) Stochastic programming (90C15) Approximation algorithms (68W25) Randomized algorithms (68W20)

Related Items (25)

Robust two-stage combinatorial optimization problems under convex second-stage cost uncertainty ⋮ Approximation algorithms for stochastic combinatorial optimization problems ⋮ K-Adaptability in Two-Stage Robust Binary Programming ⋮ An Approximation Algorithm for the Two-Stage Distributionally Robust Facility Location Problem ⋮ An approximation algorithm for the \(k\)-level stochastic facility location problem ⋮ Submodular reassignment problem for reallocating agents to tasks with synergy effects ⋮ Thresholded covering algorithms for robust and max-min optimization ⋮ Universal Algorithms for Clustering Problems ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Approximation Algorithms for Stochastic and Risk-Averse Optimization ⋮ Exact Quantization of Multistage Stochastic Linear Problems ⋮ Totally unimodular stochastic programs ⋮ Approximability of the two-stage stochastic knapsack problem with discretely distributed weights ⋮ Provably Near-Optimal Approximation Schemes for Implicit Stochastic and Sample-Based Dynamic Programs ⋮ Improved bounds in stochastic matching and optimization ⋮ An improved per-scenario bound for the two-stage stochastic facility location problem ⋮ LP-rounding approximation algorithms for two-stage stochastic fault-tolerant facility location problem ⋮ Simpler and Better Algorithms for Minimum-Norm Load Balancing ⋮ An approximation algorithm for the stochastic fault-tolerant facility location problem ⋮ Improved approximation algorithms for the facility location problems with linear/submodular penalties ⋮ Maximizing Expected Utility for Stochastic Combinatorial Optimization Problems ⋮ Sampling-Based Approximation Schemes for Capacitated Stochastic Inventory Control Models ⋮ An approximation algorithm for stochastic multi-level facility location problem with soft capacities ⋮ Fully polynomial time \((\Sigma,\Pi)\)-approximation schemes for continuous nonlinear newsvendor and continuous stochastic dynamic programs

This page was built for publication: An approximation scheme for stochastic linear programming and its application to stochastic integer programs