Tight Lower Bounds for Approximate & Exact k-Center in Rd

Chitnis, R. and Saurabh, Nitin (2022) Tight Lower Bounds for Approximate & Exact k-Center in Rd. In: 38th International Symposium on Computational Geometry, SoCG 2022, 7 June 2022 through 10 June 2022, Berlin.

Text
Leibniz_International_Proceedings.pdf - Published Version
Available under License Creative Commons Attribution.
Download (875kB)

Abstract

In the discrete k-Center problem, we are given a metric space (P, dist) where \textbarP \textbar = 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 algorithm1 for this problem in d-dimensional Euclidean space2 which runs in O(dn log k) + ( k? )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)Â· ( 1? )o(k1-1/d) Â·no(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) 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'14 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'98, Algorithmica'02 which runs in nO(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) Â· no(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. Â© Rajesh Chitnis and Nitin Saurabh; licensed under Creative Commons License CC-BY 4.0

[error in script]

IITH Creators: