1 Search Results for "Zats, Roded"

Document

APPROX

DOI: 10.4230/LIPIcs.APPROX/RANDOM.2022.37

Fair Correlation Clustering in General Graphs

Authors: Roy Schwartz and Roded Zats

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

Abstract

We consider the family of Correlation Clustering optimization problems under fairness constraints. In Correlation Clustering we are given a graph whose every edge is labeled either with a + or a -, and the goal is to find a clustering that agrees the most with the labels: + edges within clusters and - edges across clusters. The notion of fairness implies that there is no over, or under, representation of vertices in the clustering: every vertex has a color and the distribution of colors within each cluster is required to be the same as the distribution of colors in the input graph. Previously, approximation algorithms were known only for fair disagreement minimization in complete unweighted graphs. We prove the following: (1) there is no finite approximation for fair disagreement minimization in general graphs unless P = NP (this hardness holds also for bicriteria algorithms); and (2) fair agreement maximization in general graphs admits a bicriteria approximation of ≈ 0.591 (an improved ≈ 0.609 true approximation is given for the special case of two uniformly distributed colors). Our algorithm is based on proving that the sticky Brownian motion rounding of [Abbasi Zadeh-Bansal-Guruganesh-Nikolov-Schwartz-Singh SODA'20] copes well with uncut edges.

Cite as

Roy Schwartz and Roded Zats. Fair Correlation Clustering in General Graphs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 245, pp. 37:1-37:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{schwartz_et_al:LIPIcs.APPROX/RANDOM.2022.37,
  author =	{Schwartz, Roy and Zats, Roded},
  title =	{{Fair Correlation Clustering in General Graphs}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)},
  pages =	{37:1--37:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-249-5},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{245},
  editor =	{Chakrabarti, Amit and Swamy, Chaitanya},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2022.37},
  URN =		{urn:nbn:de:0030-drops-171591},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2022.37},
  annote =	{Keywords: Correlation Clustering, Approximation Algorithms, Semi-Definite Programming}
}

Refine by Author
1 Schwartz, Roy
1 Zats, Roded

Refine by Classification
1 Theory of computation → Facility location and clustering

Refine by Keyword
1 Approximation Algorithms
1 Correlation Clustering
1 Semi-Definite Programming

Refine by Type
1 document

Refine by Publication Year
1 2022

1 Search Results for "Zats, Roded"

Fair Correlation Clustering in General Graphs

Abstract

Cite as

Thanks for your feedback!

Could not send message