DROPS

Document

DOI: 10.4230/LIPIcs.ESA.2023.69

An Improved Approximation Algorithm for the Max-3-Section Problem

Authors: Dor Katzelnick, Aditya Pillai, Roy Schwartz, and Mohit Singh

Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)

Abstract

We consider the Max--Section problem, where we are given an undirected graph G=(V,E)equipped with non-negative edge weights w: E → R_+ and the goal is to find a partition of V into three equisized parts while maximizing the total weight of edges crossing between different parts. Max-3-Section is closely related to other well-studied graph partitioning problems, e.g., Max-Cut, Max-3-Cut, and Max-Bisection. We present a polynomial time algorithm achieving an approximation of 0.795, that improves upon the previous best known approximation of 0.673. The requirement of multiple parts that have equal sizes renders Max-3-Section much harder to cope with compared to, e.g., Max-Bisection. We show a new algorithm that combines the existing approach of Lassere hierarchy along with a random cut strategy that suffices to give our result.

Cite as

Dor Katzelnick, Aditya Pillai, Roy Schwartz, and Mohit Singh. An Improved Approximation Algorithm for the Max-3-Section Problem. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 69:1-69:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{katzelnick_et_al:LIPIcs.ESA.2023.69,
  author =	{Katzelnick, Dor and Pillai, Aditya and Schwartz, Roy and Singh, Mohit},
  title =	{{An Improved Approximation Algorithm for the Max-3-Section Problem}},
  booktitle =	{31st Annual European Symposium on Algorithms (ESA 2023)},
  pages =	{69:1--69:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-295-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{274},
  editor =	{G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2023.69},
  URN =		{urn:nbn:de:0030-drops-187229},
  doi =		{10.4230/LIPIcs.ESA.2023.69},
  annote =	{Keywords: Approximation Algorithms, Semidefinite Programming, Max-Cut, Max-Bisection}
}

Document

APPROX

DOI: 10.4230/LIPIcs.APPROX/RANDOM.2020.49

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

Authors: Dor Katzelnick and Roy Schwartz

Published in: LIPIcs, Volume 176, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)

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.

Cite as

Dor Katzelnick and Roy Schwartz. Maximizing the Correlation: Extending Grothendieck’s Inequality to Large Domains. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 176, pp. 49:1-49:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{katzelnick_et_al:LIPIcs.APPROX/RANDOM.2020.49,
  author =	{Katzelnick, Dor and Schwartz, Roy},
  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 =	{Byrka, Jaros{\l}aw and Meka, Raghu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2020.49},
  URN =		{urn:nbn:de:0030-drops-126525},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2020.49},
  annote =	{Keywords: Correlation Clustering, Grothendieck’s Inequality, Approximation}
}

Search Results

Documents authored by Katzelnick, Dor

An Improved Approximation Algorithm for the Max-3-Section Problem

Abstract

Cite as

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

Abstract

Cite as

Thanks for your feedback!

Could not send message