Handling LP-Rounding for Hierarchical Clustering and Fitting Distances by Ultrametrics
by
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. He received his Ph.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.
Prof. Kao visits TU Dortmund (September 2025 - July 2027) under Humboldt Fellow program, hosted by the Area Chair, JJ Chen, of Resource-Aware Machine Learning.
Prof. Dr. Jian-Jia Chen
Dr. Jens Buß