Tight Lower Bounds for Approximate & Exact k-Center in ?^d

In the discrete k-Center problem, we are given a metric space (P,dist) where |P| = n and the goal is to select a set C ? P of k centers which minimizes the maximum distance of a point in P from its nearest center. For any ? > 0, Agarwal and Procopiuc [SODA \u2798, Algorithmica \u2702] designed an (1+?)-approximation algorithm for this problem in d-dimensional Euclidean space which runs in O(dn log k) + (k/?)^{O (k^{1-1/d})}? n^{O(1)} time. In this paper we show that their algorithm is essentially optimal: if for some d ? 2 and some computable function f, there is an f(k)?(1/?)^{o (k^{1-1/d})} ? n^{o (k^{1-1/d})} time algorithm for (1+?)-approximating the discrete k-Center on n points in d-dimensional Euclidean space then the Exponential Time Hypothesis (ETH) fails. We obtain our lower bound by designing a gap reduction from a d-dimensional constraint satisfaction problem (CSP) to discrete d-dimensional k-Center. This reduction has the property that there is a fixed value ? (depending on the CSP) such that the optimal radius of k-Center instances corresponding to satisfiable and unsatisfiable instances of the CSP is < 1 and ? (1+?) respectively. Our claimed lower bound on the running time for approximating discrete k-Center in d-dimensions then follows from the lower bound due to Marx and Sidiropoulos [SoCG \u2714] for checking the satisfiability of the aforementioned d-dimensional CSP. As a byproduct of our reduction, we also obtain that the exact algorithm of Agarwal and Procopiuc [SODA \u2798, Algorithmica \u2702] which runs in n^{O (d? k^{1-1/d})} time for discrete k-Center on n points in d-dimensional Euclidean space is asymptotically optimal. Formally, we show that if for some d ? 2 and some computable function f, there is an f(k)?n^{o (k^{1-1/d})} time exact algorithm for the discrete k-Center problem on n points in d-dimensional Euclidean space then the Exponential Time Hypothesis (ETH) fails. Previously, such a lower bound was only known for d = 2 and was implicit in the work of Marx [IWPEC \u2706]