Dimension-Free Parameterized Approximation Schemes for Hybrid Clustering
Ameet Gadekar, Tanmay Inamdar · 2025
Read Dimension-Free Parameterized Approximation Schemes for Hybrid Clustering by Ameet Gadekar, Tanmay Inamdar (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2501-03663.txt.
Description
Ameet Gadekar and Tanmay Inamdar speed up near-optimal clustering when the data live in very high dimensions, in a 2025 paper. Hybrid k-clustering blends two classic goals: covering points with balls of a set radius, and minimizing total distance beyond that radius. An earlier algorithm achieved a double approximation guarantee, but its running time exploded exponentially with the dimension.
The new scheme keeps the same bicriteria guarantee while its cost depends only on the number of clusters and the accuracy parameter, not the dimension. That resolves an open question from the earlier work. The techniques travel beyond Euclidean space to doubling spaces, minor-free metrics, and bounded-treewidth metrics, and they yield similar schemes for several related clustering variants. High-dimensional data no longer prices the method out.
Catalog record
| CREATOR | Ameet Gadekar, Tanmay Inamdar |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 74 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2501-03663