Partially Doubling Metrics Clustering

Auto-generated stub. Edit this file to add more details.

Approximation schemes for $k$-median or facility location problems where only one partition ($X$ or $Y$) of the input points possesses a bounded doubling dimension.

Why It Matters

This extends the class of metrics for which near-linear time approximation schemes exist for the $k$-median problem beyond purely doubling metrics.

Evidence

the case when either X or Y has bounded doubling dimension (but the other set not)

Related Papers

• openalex-2603.24336-near-linear-time-approximation-schemes-for-clustering-of-par