A Tight VC-Dimension Analysis of Clustering Coresets with Applications

Abstract

We consider coresets for k-clustering problems, where the goal is to assign points to centers minimizing powers of distances. A popular example is the k-median objective _p_c Cdist(p,C). Given a point set P, a coreset is a small weighted subset that approximates the cost of P for all candidate solutions C up to a (1 ) multiplicative factor. In this paper, we give a sharp VC-dimension based analysis for coreset construction. As a consequence, we obtain improved k-median coreset bounds for the following metrics: Coresets of size O(k^-2) for shortest path metrics in planar graphs, improving over the bounds O(k^-6) by [Cohen-Addad, Saulpic, Schwiegelshohn, STOC'21] and O(k^2^-4) by [Braverman, Jiang, Krauthgamer, Wu, SODA'21]. Coresets of size O(kd^-2 m) for clustering d-dimensional polygonal curves of length at most m with curves of length at most with respect to Frechet metrics, improving over the bounds O(k^3d^-3 m) by [Braverman, Cohen-Addad, Jiang, Krauthgamer, Schwiegelshohn, Toftrup, and Wu, FOCS'22] and O(k^2d^-2 m |P|) by [Conradi, Kolbe, Psarros, Rohde, SoCG'24].

Tasks

Reproductions