2022/03/16 by Chitnis, Rajesh, Saurabh, Nitin
#Computational Complexity (cs.CC) #Computational Geometry (cs.CG) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2203.08328
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 '98, Algorithmica '02] designed an (1+ε)-approximation algorithm for this problem in d-dimensional Euclidean space which runs in O(dnlog k) + (\dfrackε)^O(k1-1/d)⋅ nO(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)⋅ (\dfrac1ε)^o(k1-1/d) ⋅ n^o(k1-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) defined by Marx and Sidiropoulos [SoCG '14] to discrete d-dimensional k-center. As a byproduct of our reduction, we also obtain that the exact algorithm of Agarwal and Procopiuc [SODA '98, Algorithmica '02] which runs in n^O(d⋅ k1-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(k1-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 '06]. [see paper for full abstract]