BEGIN:VCALENDAR
VERSION:2.0
PRODID:icalendar-ruby
CALSCALE:GREGORIAN
METHOD:PUBLISH
BEGIN:VTIMEZONE
TZID:Europe/Vienna
BEGIN:DAYLIGHT
DTSTART:20260329T030000
TZOFFSETFROM:+0100
TZOFFSETTO:+0200
RRULE:FREQ=YEARLY;BYDAY=-1SU;BYMONTH=3
TZNAME:CEST
END:DAYLIGHT
BEGIN:STANDARD
DTSTART:20251026T020000
TZOFFSETFROM:+0200
TZOFFSETTO:+0100
RRULE:FREQ=YEARLY;BYDAY=-1SU;BYMONTH=10
TZNAME:CET
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTAMP:20260424T143339Z
UID:6960c7d51ac45346543365@ist.ac.at
DTSTART:20260119T113000
DTEND:20260119T123000
DESCRIPTION:Speaker: David Rasmussen Lolck\nhosted by Monika Henzinger\nAbs
 tract: Correlation clustering is a well-studied problem\, first proposed b
 y Bansal\, Blum\, and Chawla (2004). The input is an unweighted\, undirect
 ed\, simple graph. The goal is to cluster (partition) the vertices so as t
 o minimize the number of edges between vertices in different clusters and 
 missing edges between vertices inside the same cluster. This problem has a
  wide number of applications in data mining and machine learning. We will 
 focus on the dynamic version of this problem\, where edges are added or de
 leted one by one\, and the goal is to maintain a clustering during these u
 pdates. This talk will present a general framework that transforms existin
 g static correlation clustering algorithms into fully-dynamic ones that wo
 rk against an adaptive adversary. In this talk\, I will show how to apply 
 the framework to known efficient static correlation clustering algorithms\
 , starting from the classic 3-approximate Pivot algorithm by Ailon\, Chari
 kar\, and Newman (2008). Applied to the recent near-linear 1.485-approxima
 tion algorithm by Cao et al. (2025)\, we get a 1.485-approximation fully-d
 ynamic algorithm that works with worst-case constant update time. The orig
 inal static algorithm gets its approximation ratio with constant probabili
 ty\, and we get the same against an adaptive adversary. Previous dynamic a
 lgorithms for correlation clustering had approximation ratios around 3 in 
 expectation against oblivious adversaries.
LOCATION:Central Bldg / O1 / Mondi 2a (I01.O1.008)\, ISTA
ORGANIZER:achaturv@ist.ac.at
SUMMARY:David Rasmussen Lolck: TCS Talk - Static to Dynamic Correlation Clu
 stering
URL:https://talks-calendar.ista.ac.at/events/6229
END:VEVENT
END:VCALENDAR