License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2017.32
URN: urn:nbn:de:0030-drops-84003
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8400/
Go to the corresponding LIPIcs Volume Portal

Guruganesh, Guru ; Lee, Euiwoong

Understanding the Correlation Gap For Matchings

pdf-format:
LIPIcs-FSTTCS-2017-32.pdf (0.5 MB)

Abstract

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.

BibTeX - Entry

@InProceedings{guruganesh_et_al:LIPIcs:2018:8400,
  author =	{Guru Guruganesh and Euiwoong Lee},
  title =	{{Understanding the Correlation Gap For Matchings}},
  booktitle =	{37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017)},
  pages =	{32:1--32:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-055-2},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{93},
  editor =	{Satya Lokam and R. Ramanujam},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/8400},
  URN =		{urn:nbn:de:0030-drops-84003},
  doi =		{10.4230/LIPIcs.FSTTCS.2017.32},
  annote =	{Keywords: Mathings, Randomized Algorithms, Correlation Gap}
}

Keywords: Mathings, Randomized Algorithms, Correlation Gap
Collection: 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017)
Issue Date: 2018
Date of publication: 12.02.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI