Matteo Russo, Sapienza University of Rome

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. Given a point set P, a coreset C is a small weighted subset that approximates the cost of P for all candidate solutions up to an epsilon 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: 
- Shortest path metrics in planar graphs (and minor free graphs);
- Frechet metrics for d-dimensional polygonal curves of length at most m with curves of length at most ell.

See: https://theory.cs.rutgers.edu/theory_seminar