Beyond 2-Approximation for k -Center in Graphs
Ce Jin, Yael Kirkpatrick, Virginia Vassilevska Williams, Nicole Wein · Society for Industrial and Applied Mathematics eBooks · 2025
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 nk-o(1) time under the Strong Exponential Time Hypothesis (SETH).