Department of Computer, Control and Management Engineering

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)