A Tight VC-dimension Analysis of Clustering Coresets

Start Date: February 26, 2025
Event Start Time: 11:00 AM
Event End Time: 12:00 PM
Seminar Series: Theoretical Computer Science Seminar
Presenter(s): Matteo Russo - Sapienza University of Rome
Event Location: Conference Room 301 | Rutgers University | CoRE Building | 96 Frelinghuysen Road
Event Additional Info: <p>See: <a href="https://theory.cs.rutgers.edu/theory_seminar">https://theory.cs.rutgers.edu/theory_seminar</a></p>
Presentation Type: Stand Alone Presentation
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.

Events