Name
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2018 | 10.1007/s00453-017-0383-4 | Algorithmica |
Keywords | DocType | Volume |
Stochastic optimization,Linear programming,Approximation algorithms,Randomized algorithms | Journal | 80 |
Issue | ISSN | Citations |
11 | 0178-4617 | 4 |
PageRank | References | Authors |
0.40 | 16 | 5 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Alok Baveja | 1 | 120 | 11.99 |
| Amit Chavan | 2 | 42 | 4.13 |
| Andrei Nikiforov | 3 | 4 | 0.73 |
| Aravind Srinivasan | 4 | 3531 | 291.42 |
| Pan Xu | 5 | 49 | 9.32 |