BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Drupal iCal API//EN
X-WR-CALNAME:Events items teaser
X-WR-TIMEZONE:America/Toronto
BEGIN:VTIMEZONE
TZID:America/Toronto
X-LIC-LOCATION:America/Toronto
BEGIN:DAYLIGHT
TZNAME:EDT
TZOFFSETFROM:-0500
TZOFFSETTO:-0400
DTSTART:20240310T070000
END:DAYLIGHT
BEGIN:STANDARD
TZNAME:EST
TZOFFSETFROM:-0400
TZOFFSETTO:-0500
DTSTART:20231105T060000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
UID:69cfbfc3d4096
DTSTART;TZID=America/Toronto:20240607T153000
SEQUENCE:0
TRANSP:TRANSPARENT
DTEND;TZID=America/Toronto:20240607T163000
URL:https://uwaterloo.ca/combinatorics-and-optimization/events/tutte-colloq
 uium-euiwoong-lee
SUMMARY:Tutte Colloquium - Euiwoong Lee
CLASS:PUBLIC
DESCRIPTION:TITLE: Recent Progresses on Correlation Clustering\n\nSPEAKER:
 \n Euiwoong Lee\n\nAFFILIATION:\n University of Michigan\n\nLOCATION:\n MC
  5501\n\nABSTRACT: Correlation Clustering is one of the most well-studied
 \ngraph clustering problems. The input is a complete graph where each\nedg
 e is labeled either \"+\" or \"-\"\, and the goal is to partition the\nver
 tex set into (an arbitrary number of) clusters to minimize (the\nnumber of
  + edges between different clusters) + (the number of - edges\nwithin the 
 same cluster). Until recently\, the best polynomial-time\napproximation ra
 tio was 2.06\, nearly matching the integrality gap of 2\nfor the standard 
 LP relaxation. Since 2022\, we have bypassed this\nbarrier and progressive
 ly improved the approximation ratio\, with the\ncurrent ratio being 1.44. 
 Based on a new relaxation inspired by the\nSherali-Adams hierarchy\, the a
 lgorithm introduces and combines several\ntools considered in different co
 ntexts\, including \"local to global\ncorrelation rounding\" and \"combina
 torial preclusering\". In this talk\,\nI will describe the current algorit
 hm as well as how it has been\ninspired by various viewpoints. Joint work 
 with Nairen Cao\, Vincent\nCohen-Addad\, Shi Li\, Alantha Newman\, and Luk
 as Vogl.
DTSTAMP:20260403T132523Z
END:VEVENT
END:VCALENDAR