Beyond 2-Approximation for k-Center in Graphs

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 + ε)-approximation algorithms for every ε > 0 running in near-linear time. The conventional wisdom is that the problem is closed, as (2 -ε)approximation is NP-hard when k is part of the input, and for constant k ≥ 2 it requires n k-o(1) time under the Strong Exponential Time Hypothesis (SETH).

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 (2-ε, O(1)) approximations. We provide several algorithms that achieve such approximations for all integers k with running time O(n k-δ ) for δ > 0. For instance, for every k ≥ 2, we obtain an O(mn + n k/2+1 ) time 2 -1 2k-1 , 1 -1 2k-1approximation to k-Center, and for every k ≥ 10 we obtain an (3/2, 1/2)-approximation algorithm running in n k-1+1/(k+1)+o( 1) time. For 2-Center we also obtain an Õ(mn ω/3 ) time (5/3, 2/3)-approximation algorithm, where ω < 2.372 is the fast matrix multiplication exponent. Notably, the running time of this 2-Center algorithm is faster than the time needed to compute APSP.

Our second set of results are strong fine-grained lower bounds for k-Center. We show that our (3/2, O(1))-approximation algorithm is optimal, under SETH, as any (3/2 -ε, O(1))-approximation algorithm requires n k-o(1) time. We also give a time/approximation trade-off: under SETH, for any integer t ≥ 1, n k/t 2 -1-o(1) time is needed for any (2 -1/(2t -1), O(1))-approximation algorithm for k-Center. This explains why our (2 -ε, O(1)) approximation algorithms have k appearing in the exponent of the running time. Our reductions also imply that, assuming ETH, the approximation ratio 2 of the known near-linear time algorithms cannot be improved by any algorithm whose running time is a polynomial independent of k, even if one allows additive error.