Beyond 2-approximation for k-Center in Graphs

Ce Jin, Yael Kirkpatrick, Virginia Vassilevska Williams +1

We consider the classical $k$-Center problem in undirected graphs. The problem is known to have a polynomial-time 2-approximation. There are even $(2+\epsilon )$-approximations r…