17 czerwca 2025 09:00
[Seminarium ZOK] Changyeol Lee: Handling LP-Rounding for Hierarchical Clustering and Fitting Distances by Ultrametrics[Seminarium ZOK]
Abstract:
We consider hierarchical correlation clustering (HCC), a
generalization of correlation clustering to a hierarchical setting.
Given a vertex set V and ℓ layers, where each layer consists of an
edge set on V and an associated non-negative weight, the goal is to
find a hierarchical clustering that minimizes the weighted sum of the
number of disagreements–defined as inter-cluster edges and
intra-cluster non-edges. Here, a hierarchical clustering is a sequence
of partitions such that each partition at a lower layer refines (i.e.,
subdivides) the partition at the layer above.
HCC is a natural formulation for the ultrametric fitting problem under
the L1-norm (a.k.a. numerical taxonomy), which has been extensively
studied since the 1970s. Recently, Cohen-Addad, Das, Kipouridis,
Parotsidis, and Thorup (FOCS’21; J.ACM’24) made a breakthrough by
giving the first constant-factor approximation algorithm; however,
their approximation ratio is large (over 1000). We present a simple
yet powerful LP-rounding framework that significantly improves the
ratio to 25.7846. Moreover, our framework naturally extends to
ultrametric violation distance (i.e., ultrametric fitting problem
under the L0-norm), yielding a 5-approximation algorithm that matches
the best-known result by Charikar and Gao (SODA’24).
In this talk, I will introduce our LP-rounding framework and explain
how it can be applied to HCC and ultrametric violation distance.
Joint work with Hyung-Chan An, Mong-Jen Kao, and Mu-Ting Lee.