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

אירועים

Maximizing the Correlation: Extending Grothendieck’s Inequality to Large Domains
event speaker icon
דור קצלניק, הרצאה סמינריונית למגיסטר
event date icon
יום רביעי, 23.12.2020, 12:30
event location icon
הרצאה באמצעות זום: https://technion.zoom.us/j/95612638603
event speaker icon
מנחה:  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.
[בחזרה לאינדקס האירועים]