2026-07-20T10:52:15Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:5299 2024-03-06T10:36:15Z ddc:004 open_access

Improved Bounds in Stochastic Matching and Optimization Baveja, Alok Chavan, Amit Nikiforov, Andrei Srinivasan, Aravind Xu, Pan stochastic matching approximation algorithms sampling complexity 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). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Alok Baveja and Amit Chavan and Andrei Nikiforov and Aravind Srinivasan and Pan Xu 2015 Is Part Of LIPIcs, Volume 40, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX-RANDOM.2015.124 urn:nbn:de:0030-drops-52991 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2015.124 eng https://creativecommons.org/licenses/by/3.0/legalcode