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

The Taub Faculty of Computer Science Events and Talks

Maximizing the Correlation: Extending Grothendieck’s Inequality to Large Domains
event speaker icon
Dor Katzelnick (M.Sc. Thesis Seminar)
event date icon
Wednesday, 23.12.2020, 12:30
event location icon
Zoom Lecture: https://technion.zoom.us/j/95612638603
event speaker icon
Advisor: Dr. Roy Schwartz
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.