BARC talk by Mong-Jen Kao
Wednesday, October 1, 2025, Mong-Jen Kao, professor in the National Yang-Ming Chiao-Tung University, China, will give a talk on "Handling LP-Rounding for Hierarchical Clustering and Fitting Distances by Ultrametrics".
Abstract:
We consider the classic correlation clustering problem in the hierarchical setting. Given a complete graph G=(V,E) and \ell layers of input information, where the input of each layer consists of a nonnegative weight and a labeling of the edges with either + or -, this problem seeks to compute for each layer a partition of V such that the partition for any non-top layer subdivides the partition in the upper-layer and the weighted number of disagreements over the layers is minimized. In this work we make both conceptual and technical contributions towards the hierarchical clustering problem. We present a simple paradigm that facilitates LP-rounding in hierarchical clustering, illustrated with an algorithm providing an improved approximation guarantee of 25.7846 for the hierarchical correlation clustering problem. Our techniques reveal surprising new properties of the formulation used in previous works for hierarchical clustering over the past two decades. This provides an interpretation on the core problem in hierarchical clustering as the problem of finding cuts with prescribed properties regarding average distances. We further illustrate this perspective by showing that a direct application of the techniques gives a simple alternative to the state-of-the-art result for the ultrametric violation distance problem.
Bio:
Mong-Jen Kao is a professor in the Department of Computer Science at the National Yang-Ming Chiao-Tung University (NYCU). Prior to joining NYCU, he was with the department of CSIE, National Chung-Cheng University, as an assistant professor and IIS, Academia Sinica, as a postdoc researcher. Mong-Jen received hisPh.D. from the department of CSIE, National Taiwan University, where he was very fortunate to work under the guidance of Academician D.T. Lee. His research interests primarily surround the design and analysis of approximation algorithms for various combinatorial optimization problems. He enjoys the intriguing exploration process for unknowns that are important in computer science.
Host:
Mikkel Thorup