BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//CERN//INDICO//EN
BEGIN:VEVENT
SUMMARY:Handling LP-Rounding for Hierarchical Clustering and Fitting Dista
 nces by Ultrametrics [Oberseminar Discrete Optimization]
DTSTART:20260810T161500Z
DTEND:20260810T171500Z
DTSTAMP:20260716T192800Z
UID:indico-event-1393@math-events.uni-bonn.de
DESCRIPTION:Speakers: Hyung-Chan An (Yonsei University)\n\nIn this talk\, 
 we present an improved approximation algorithm for hierarchical correlatio
 n clustering. Given L layers of complete graphs on a common vertex set V\,
  where each edge is labeled either + or -\, the problem is to compute a cl
 ustering of V for each layer so that lower-layer clusterings refine upper-
 layer ones and the total weighted number of disagreements over all layers 
 is minimized. Here\, a + edge is counted as a disagreement if its endpoint
 s are separated\, and a - edge if its endpoints are placed in the same clu
 ster. This problem is both a natural generalization of correlation cluster
 ing (the case L=1) and a formulation of the L1 ultrametric fitting problem
  arising in numerical taxonomy. Unlike the single-layer setting\, for whic
 h substantial algorithmic progress has been made in recent years\, the hie
 rarchical case has seen little progress since the first constant-factor ap
 proximation algorithm of Cohen-Addad\, Das\, Kipouridis\, Parotsidis\, and
  Thorup. We give a new LP-rounding algorithm achieving an approximation ra
 tio of 25.8\, significantly improving the previous guarantee.\nJoint work 
 with Mong-Jen Kao\, Changyeol Lee\, and Mu-Ting Lee (FOCS '25).\n \nThe O
 berseminar takes place in the Seminarraum\, 1st floor. Participants are in
 vited to have coffee or tea in the lounge before.\n \n\nhttps://math-even
 ts.uni-bonn.de/event/1393/
LOCATION:Arithmeum\, Lennéstr.\,  2 - Seminarraum (Arithmeum / Research I
 nstitute for Discrete Mathematics)
URL:https://math-events.uni-bonn.de/event/1393/
END:VEVENT
END:VCALENDAR