Prof. Dr. Hyung-Chan An (Yonsei University, South Korea)
Handling LP-Rounding for Hierarchical Clustering and Fitting Distances by Ultrametrics abstract
Abstract:
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).
13:30 • ETH Zentrum, Rämistrasse 101, Zürich, Building HG, Room G 19.1