Handling LP-Rounding for Hierarchical Clustering and Fitting Distances by UltrametricsOberseminar Discrete Optimization

by Hyung-Chan An (Yonsei University)

Monday Aug 10, 2026, 6:15 PM → 7:15 PM Europe/Berlin

Arithmeum, Lennéstr., 2 - Seminarraum (Arithmeum / Research Institute for Discrete Mathematics)

In this talk, we present an improved approximation algorithm for hierarchical correlation 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 clustering 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 endpoints are separated, and a - edge if its endpoints are placed in the same cluster. This problem is both a natural generalization of correlation clustering (the case L=1) and a formulation of the L1 ultrametric fitting problem arising in numerical taxonomy. Unlike the single-layer setting, for which substantial algorithmic progress has been made in recent years, the hierarchical case has seen little progress since the first constant-factor approximation algorithm of Cohen-Addad, Das, Kipouridis, Parotsidis, and Thorup. We give a new LP-rounding algorithm achieving an approximation ratio of 25.8, significantly improving the previous guarantee.

Joint work with Mong-Jen Kao, Changyeol Lee, and Mu-Ting Lee (FOCS '25).

 

The Oberseminar takes place in the Seminarraum, 1st floor. Participants are invited to have coffee or tea in the lounge before.