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.APPROX/RANDOM.2020.49
URN: urn:nbn:de:0030-drops-126525
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12652/
Go to the corresponding LIPIcs Volume Portal

Katzelnick, Dor ; Schwartz, Roy

Maximizing the Correlation: Extending Grothendieck’s Inequality to Large Domains

pdf-format:
LIPIcs-APPROX49.pdf (0.6 MB)

Abstract

Correlation Clustering is an elegant model where given a graph with edges labeled + or -, the goal is to produce a clustering that agrees the most with the labels: + edges should reside within clusters and - edges should cross between clusters. In this work we study the MaxCorr objective, aiming to find a clustering that maximizes the difference between edges classified correctly and incorrectly. We focus on the case of bipartite graphs and present an improved approximation of 0.254, improving upon the known approximation of 0.219 given by Charikar and Wirth [FOCS`2004] and going beyond the 0.2296 barrier imposed by their technique. Our algorithm is inspired by Krivine’s method for bounding Grothendieck’s constant, and we extend this method to allow for more than two clusters in the output. Moreover, our algorithm leads to two additional results: (1) the first known approximation guarantees for MaxCorr where the output is constrained to have a bounded number of clusters; and (2) a natural extension of Grothendieck’s inequality to large domains.

BibTeX - Entry

@InProceedings{katzelnick_et_al:LIPIcs:2020:12652,
  author =	{Dor Katzelnick and Roy Schwartz},
  title =	{{Maximizing the Correlation: Extending Grothendieck’s Inequality to Large Domains}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)},
  pages =	{49:1--49:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-164-1},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{176},
  editor =	{Jaros{\l}aw Byrka and Raghu Meka},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/12652},
  URN =		{urn:nbn:de:0030-drops-126525},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2020.49},
  annote =	{Keywords: Correlation Clustering, Grothendieck’s Inequality, Approximation}
}

Keywords: Correlation Clustering, Grothendieck’s Inequality, Approximation
Collection: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)
Issue Date: 2020
Date of publication: 11.08.2020

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