Date: May 4, 2026
Time: 3:45-5 p.m.
Location: Gates Hall, 122 or Click here to attend via Zoom
Speaker: Hyung-Chan An, Yonsei University
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.
Bio: Hyung-Chan An is an Associate Professor in the Department of Computer Science and Engineering at Yonsei University. His research interests include approximation algorithms, online algorithms, combinatorial optimization, and their applications to engineering problems. Before joining Yonsei University, he was a Postdoctoral Researcher at École Polytechnique Fédérale de Lausanne (EPFL). He received his Ph.D. in Computer Science from Cornell University and his B.S. in Computer Science and Engineering from Seoul National University.