Chitnis, Rajesh ;
Saurabh, Nitin
Tight Lower Bounds for Approximate & Exact kCenter in ℝ^d
Abstract
In the discrete kCenter 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 ddimensional Euclidean space which runs in O(dn log k) + (k/ε)^{O (k^{11/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^{11/d})} ⋅ n^{o (k^{11/d})} time algorithm for (1+ε)approximating the discrete kCenter on n points in ddimensional Euclidean space then the Exponential Time Hypothesis (ETH) fails.
We obtain our lower bound by designing a gap reduction from a ddimensional constraint satisfaction problem (CSP) to discrete ddimensional kCenter. This reduction has the property that there is a fixed value ε (depending on the CSP) such that the optimal radius of kCenter 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 kCenter in ddimensions then follows from the lower bound due to Marx and Sidiropoulos [SoCG '14] for checking the satisfiability of the aforementioned ddimensional 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 n^{O (d⋅ k^{11/d})} time for discrete kCenter on n points in ddimensional 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^{11/d})} time exact algorithm for the discrete kCenter problem on n points in ddimensional 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].
BibTeX  Entry
@InProceedings{chitnis_et_al:LIPIcs.SoCG.2022.28,
author = {Chitnis, Rajesh and Saurabh, Nitin},
title = {{Tight Lower Bounds for Approximate \& Exact kCenter in \mathbb{R}^d}},
booktitle = {38th International Symposium on Computational Geometry (SoCG 2022)},
pages = {28:128:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772273},
ISSN = {18688969},
year = {2022},
volume = {224},
editor = {Goaoc, Xavier and Kerber, Michael},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/16036},
URN = {urn:nbn:de:0030drops160365},
doi = {10.4230/LIPIcs.SoCG.2022.28},
annote = {Keywords: kcenter, Euclidean space, Exponential Time Hypothesis (ETH), lower bound}
}
01.06.2022
Keywords: 

kcenter, Euclidean space, Exponential Time Hypothesis (ETH), lower bound 
Seminar: 

38th International Symposium on Computational Geometry (SoCG 2022)

Issue date: 

2022 
Date of publication: 

01.06.2022 