דלג לתוכן (מקש קיצור 's')
אירועים

אירועים והרצאות בפקולטה למדעי המחשב ע"ש הנרי ומרילין טאוב

חלוקה הוגנת של גרפים לאשכולות
event speaker icon
רודד זץ (הרצאה סמינריונית למגיסטר)
event date icon
יום שני, 22.08.2022, 08:30
event location icon
הרצאת זום: 7795921179
event speaker icon
מנחה: 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).