A factor \(\frac {1}{2}\) approximation algorithm for two-stage stochastic matching problems
From MaRDI portal
Publication:2488899
DOI10.1016/j.ejor.2004.10.011zbMath1111.90075OpenAlexW1966191083MaRDI QIDQ2488899
Publication date: 16 May 2006
Published in: European Journal of Operational Research (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ejor.2004.10.011
Related Items (12)
Two-stage stochastic max-weight independent set problems ⋮ Two‐stage stochastic minimum s − t cut problems: Formulations, complexity and decomposition algorithms ⋮ Risk‐averse optimization and resilient network flows ⋮ Totally unimodular stochastic programs ⋮ Sell or hold: A simple two-stage stochastic combinatorial optimization problem ⋮ Approximability of the two-stage stochastic knapsack problem with discretely distributed weights ⋮ The discrete sell or hold problem with constraints on asset values ⋮ Commitment under uncertainty: Two-stage stochastic matching problems ⋮ Hedging uncertainty: approximation algorithms for stochastic optimization problems ⋮ Two-stage stochastic matching and spanning tree problems: polynomial instances and approximation ⋮ Analysis of Sparse Cutting Planes for Sparse MILPs with Applications to Stochastic MILPs ⋮ The submodularity of two-stage stochastic maximum-weight independent set problems
Cites Work
- Unnamed Item
- Unnamed Item
- Partitioning procedures for solving mixed-variables programming problems
- Approximation algorithms and relaxations for a service provision problem on a telecommunication network
- Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
- Introduction to Stochastic Programming
- Maximum matching and a polyhedron with 0,1-vertices
- L-Shaped Linear Programs with Applications to Optimal Control and Stochastic Programming
This page was built for publication: A factor \(\frac {1}{2}\) approximation algorithm for two-stage stochastic matching problems
