A factor \(\frac {1}{2}\) approximation algorithm for two-stage stochastic matching problems

DOI10.1016/j.ejor.2004.10.011zbMath1111.90075MaRDI QIDQ2488899

Andrew J. Schaefer, Nan Kong

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

zbMATH Keywords

Matching; Combinatorial optimization; Stochastic programming; Approximation algorithms

Mathematics Subject Classification ID

90C10: Integer programming

90C27: Combinatorial optimization

Related Items

Analysis of Sparse Cutting Planes for Sparse MILPs with Applications to Stochastic MILPs, Two‐stage stochastic minimum s − t cut problems: Formulations, complexity and decomposition algorithms, Sell or hold: A simple two-stage stochastic combinatorial optimization problem, The discrete sell or hold problem with constraints on asset values, Commitment under uncertainty: Two-stage stochastic matching problems, Totally unimodular stochastic programs, The submodularity of two-stage stochastic maximum-weight independent set problems, Two-stage stochastic max-weight independent set problems, Two-stage stochastic matching and spanning tree problems: polynomial instances and approximation, Approximability of the two-stage stochastic knapsack problem with discretely distributed weights, Hedging uncertainty: approximation algorithms for stochastic optimization 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