Skip to content (access key 's')
Logo of Technion
Logo of CS Department
Logo of CS4People

The Taub Faculty of Computer Science Events and Talks

Fair Correlation Clustering In General Graphs
event speaker icon
Roded Zats (M.Sc. Thesis Seminar)
event date icon
Monday, 22.08.2022, 08:30
event location icon
Zoom Lecture: 7795921179
event speaker icon
Advisor: Prof. Roy Schwartz
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 $\approx 0.591$ (an improved $\approx 0.609$ true approximation is given for the special case of two uniformly distributed colors).