A (2 + ε)-Approximation Algorithm for Metric k-Median
Speaker:
Chris Schwiegelshohn (Aarhus University)
Data dell'evento:
Venerdì, 24 October, 2025 - 12:00
Luogo:
DIAG - Aula Magna
Contatto:
Stefano Leonardi
k-Median is a classic problem in data analysis where we aim to minimize the sum of distances of points to a set of at most k centers. It is NP-hard to solve accurately, so most algorithms either resort to approximation,or require assumptions. In this talk, we present an algorithm that synthesizes both of these lines of research to obtain a (2 + ε) approximation.
The paper appeared at STOC 2025 is joint work with Vincent Cohen-Addad (Google Research) Fabrizio Grandoni (IDSIA), Euiwoong Lee (University of Michigan), Ola Svensson (University of Lausanne)
gruppo di ricerca: