Yael Kirkpatrick, Massachusetts Institute of Technology

Abstract

In this talk we consider the classical k-Center problem in undirected graphs: given a graph G, find a set of k vertices that minimizes the biggest distance of a vertex to the set. The problem is known to have a polynomial-time 2-approximation and even (2 + ε)-approximation algorithms for every ε >0 running in near-linear time. The conventional wisdom is that the problem is closed, as a reduction from k-Dominating-Set shows that any (2 − ε)-approximation requires n^{k−o(1)} time.

Our first set of results show that one can beat the multiplicative factor of 2 in undirected unweighted graphs if one is willing to allow additional small additive error, obtaining various (2−ε, O(1)) approximations running in time O(n^{k−δ}) for any k. We will discuss the approach to these algorithms and see that when the k-Center is not a k-Dominating-Set we do in fact obtain a (2-ε)-approximation.

Our second set of results are strong fine-grained lower bounds for k-Center. We use the powerful but underutilized tool of `gap set cover’ to show that the dependence on k in the exponent in the runtime of our algorithms is necessary, and the approximation ratio 2 cannot be improved by any algorithm whose running time is a polynomial independent of k, even if one allows additive error. 

Based on joint work with Ce Jin, Virginia Vassilevska Williams and Nicole Wein, SODA25.