Improved Bounds in Stochastic Matching and Optimization
2018
Real-world problems often have parameters that are uncertain during the optimization phase; stochastic optimization or stochastic programming is a key approach introduced by Beale and by Dantzig in the 1950s to address such uncertainty. Matching is a classical problem in combinatorial optimization. Modern stochastic versions of this problem model problems in kidney exchange, for instance. We improve upon the current-best approximation bound of 3.709 for stochastic matching due to Adamczyk et al. (in: Algorithms-ESA 2015, Springer, Berlin, 2015) to 3.224; we also present improvements on Bansal et al. (Algorithmica 63(4):733–762, 2012) for hypergraph matching and for relaxed versions of the problem. These results are obtained by improved analyses and/or algorithms for rounding linear-programming relaxations of these problems.
Keywords:
- Discrete mathematics
- Combinatorics
- Combinatorial optimization
- Mathematics
- Mathematical optimization
- Linear programming
- Approximation algorithm
- Randomized algorithm
- Stochastic optimization
- Stochastic programming
- Optimization problem
- Rounding
- stochastic matching
- Theory of computation
- Hypergraph
- Sampling (statistics)
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
35
References
23
Citations
NaN
KQI