Improved Bounds in Stochastic Matching and Optimization
Alok Baveja, Amit Chavan, Andrei L. Nikiforov, Aravind Srinivasan, Pan Xu · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · 2015
We consider two fundamental problems in stochastic optimization: approximation algorithms for stochastic matching, and sampling bounds in the black-box model. For the former, we improve the current-best bound of 3.709 due to Adamczyk et al. (2015), to 3.224; we also present improvements on Bansal et al. (2012) for hypergraph matching and for relaxed versions of the problem. In the context of stochastic optimization, we improve upon the sampling bounds of Charikar et al. (2005).