Weighted ultrametric embedding with outliers gets better approximation
A $5/2$-Approximation for Weighted Ultrametric Embedding with Outliers
Data Structures and Algorithms
Summary
The problem is about finding a small weighted set of points to remove so that the remaining distances between points behave like a special type of metric called an ultrametric. This means no group of three points has a unique largest distance, which helps structure data in hierarchical ways. The authors improved the best approximation algorithm from a factor of 3 to 2.5, meaning their solution is closer to the best possible answer. They also note it’s very hard to get better than a factor of 2 by known complexity assumptions.
What this means in practice
- •For data engineers: Identify and remove minimal weighted outliers to get ultrametric representations for hierarchical clustering in large datasets.
- •For network designers: Use improved approximations to optimize network metrics that require ultrametric properties after removing irregular connections or nodes.
A theory result. No direct application yet.
Authors
Chenglin Fan
Abstract
Weighted ultrametric embedding with outliers asks for a minimum weight set of points whose deletion makes the remaining metric an ultrametric, equivalently, leaves no triple with a unique largest distance. We give a deterministic $5/2$-approximation using $O(n^5)$ arithmetic and comparison operations, improving the previous factor $3$ for arbitrary nonnegative vertex weights. Approximating the problem within any factor strictly below $2$ is UGC-hard.