2026-07-22T05:41:36Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8400 2024-03-06T10:41:59Z ddc:004 open_access

Understanding the Correlation Gap For Matchings Guruganesh, Guru Lee, Euiwoong Mathings Randomized Algorithms Correlation Gap Given a set of vertices V with |V| = n, a weight vector w in (R^+ \cup {0})^{\binom{V}{2}}, and a probability vector x In [0, 1]^{\binom{V}{2}} in the matching polytope, we study the quantity (\E_{G}[ \nu_w(G)])/(sum_(u, v) in \binom{V}{2} w_{u, v} x_{u, v}) where G is a random graph where each edge e with weight w_e appears with probability x_e independently, and let \nu_w(G) denotes the weight of the maximum matching of G. This quantity is closely related to correlation gap and contention resolution schemes, which are important tools in the design of approximation algorithms, algorithmic game theory, and stochastic optimization. We provide lower bounds for the above quantity for general and bipartite graphs, and for weighted and unweighted settings. The best known upper bound is 0.54 by Karp and Sipser, and the best lower bound is 0.4. We show that it is at least 0.47 for unweighted bipartite graphs, at least 0.45 for weighted bipartite graphs, and at least 0.43 for weighted general graphs. To achieve our results, we construct local distribution schemes on the dual which may be of independent interest. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Guru Guruganesh and Euiwoong Lee 2018 Is Part Of LIPIcs, Volume 93, 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2017.32 urn:nbn:de:0030-drops-84003 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2017.32 eng https://creativecommons.org/licenses/by/3.0/legalcode