Improved Bounds in Stochastic Matching and Optimization
Improved Bounds in Stochastic Matching and Optimization
复制标题
DOI：
10.1007/s00453-017-0383-4
复制
发表时间：
2017-10
期刊：
影响因子：
1.1
通讯作者：
Alok Baveja;Amit Chavan;Andrei Nikiforov;A. Srinivasan;Pan Xu
中科院分区：
文献类型：
--
作者：
Alok Baveja;Amit Chavan;Andrei Nikiforov;A. Srinivasan;Pan Xu
现实世界中的问题在优化阶段往往具有不确定的参数；随机优化或随机规划是Beale和Dantzig在20世纪50年代为解决这种不确定性而提出的一种关键方法。匹配问题是组合优化中的经典问题。例如，现代随机版本的这个问题的模型在肾脏交换中的问题。我们改进了Adamczyk等人关于随机匹配的当前最佳逼近界3.709。(见：算法-欧空局2015年，斯普林格，柏林，2015年)到3.224；我们还提出了对Bansal等人的改进。(算法63(4)：733-762,2012)，用于超图匹配和问题的松弛版本。这些结果是通过对这些问题的线性规划松弛进行舍入的改进的分析和/或算法获得的。
Real-world problems often have parameters that are uncertain during the optimization phase;stochastic optimizationorstochastic programmingis 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.