@article{a804ea097c0f4b8ba15a8cfd8d7599fe,
title = "Improved Bounds in Stochastic Matching and Optimization",
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.",
keywords = "Approximation algorithms, Linear programming, Randomized algorithms, Stochastic optimization",
author = "Alok Baveja and Amit Chavan and Andrei Nikiforov and Aravind Srinivasan and Pan Xu",
note = "Funding Information: Acknowledgements A preliminary version of this paper appears as part of a paper in the Proc. International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), 2015. We thank R. Ravi and the referees for their valuable comments regarding the details as well as context of this work. The research of the first author is partially supported in part by grants from British Council{\textquoteright}s UKIERI program and the United States Department of Transportation{\textquoteright}s UTRC Region II consortium (RF # 49198-25-26). The research of the fourth author is partially supported in part by NSF Awards CNS-1010789, CCF-1422569 and CCF-1749864, and by research awards from Adobe, Inc. The research of the last author is supported in part by NSF Awards CNS 1010789 and CCF 1422569. Funding Information: A preliminary version of this paper appears as part of a paper in the Proc. International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), 2015. We thank R.?Ravi and the referees for their valuable comments regarding the details as well as context of this work. The research of the first author is partially supported in part by grants from British Council?s UKIERI program and the United States Department of Transportation?s UTRC Region II consortium (RF # 49198-25-26). The research of the fourth author is partially supported in part by NSF Awards CNS-1010789, CCF-1422569 and CCF-1749864, and by research awards from Adobe, Inc. The research of the last author is supported in part by NSF Awards CNS 1010789 and CCF 1422569. Publisher Copyright: {\textcopyright} 2017, Springer Science+Business Media, LLC.",
year = "2018",
month = nov,
day = "1",
doi = "10.1007/s00453-017-0383-4",
language = "English (US)",
volume = "80",
pages = "3225--3252",
journal = "Algorithmica",
issn = "0178-4617",
publisher = "Springer New York",
number = "11",
}