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

CREATORAmeet Gadekar, Tanmay Inamdar
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE74 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2501-03663

Browse the full library · About the Tower of Babel