论文标题
$ \ mathbb {r}^d $的大约＆精确$ k $ center的紧密下限
Tight Lower Bounds for Approximate & Exact $k$-Center in $\mathbb{R}^d$
论文作者
论文摘要
在离散的$ k $ - 中心问题中，我们获得了公制空间$（p，\ texttt {dist}）$，其中$ | p | = n $，目标是选择一个$ c \ subseteq p $ $ k $中心的$ c \ subseteq p $ of $ k $中心，以最大程度地减少$ p $与最近的中心的$ p $中的最大距离。对于任何$ε> 0 $，Agarwal和Procopiuc [Soda '98，Algorithmica '02]设计了$（1 +ε）$ - 在$ d $ d $ d $二维的欧几里得空间中的近似算法，该算法在$ o（dn \ log k） +k） +k） +k） +log k） +k） +log k） \ left（\ dfrac {k}ε\ right）^{o \ left（k^{1-1/d} \ right）} \ cdot n^{o（1）} $ time。在本文中，我们表明它们的算法本质上是最佳的：如果对于某些$ d \ geq 2 $和一些可计算的函数$ f $，则有一个$ f（k）\ cdot \ left（\ dfrac {\ dfrac {1}ε\ right） n^{o\left(k^{1-1/d}\right)}$ time algorithm for $(1+ε)$-approximating the discrete $k$-center on $n$ points in $d$-dimensional Euclidean space then the Exponential Time Hypothesis (ETH) fails. 我们通过设计从Marx和Sidiropoulos [SOCG '14]定义的$ d $维约束满意度问题（CSP）的差距来获得下限，从而获得了差距。作为减少的副产品，我们还获得了Agarwal和procopiuc [Soda '98，算法'02]的确切算法，该算法以$ n^{o \ left（d \ cdot k^{1-1/d}} $ n $ k $ k $ k $ n $ dim $ n $ n $ n $ n $ dim-d $ n $ dim-dim $ n $ n $ dim-dim-dim-dim-dim-dim-dim-dim-dim-dim-dim-dim $ n $ dim-d $ dim-dim $ n $ n $ n $ n $ dim-d $ n $ dim-渐近最佳。 Formally, we show that if for some $d\geq 2$ and some computable function $f$, there is an $f(k)\cdot n^{o\left(k^{1-1/d}\right)}$ time exact algorithm for the discrete $k$-center problem on $n$ points in $d$-dimensional Euclidean space then the Exponential Time Hypothesis (ETH) fails.以前，这样的下限仅以$ d = 2 $而闻名，并且在马克思[IWPEC '06]的工作中是隐含的。 [请参阅纸张以获取完整摘要]
In the discrete $k$-center problem, we are given a metric space $(P,\texttt{dist})$ where $|P|=n$ and the goal is to select a set $C\subseteq 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(dn\log k) + \left(\dfrac{k}ε\right)^{O\left(k^{1-1/d}\right)}\cdot n^{O(1)}$ time. In this paper we show that their algorithm is essentially optimal: if for some $d\geq 2$ and some computable function $f$, there is an $f(k)\cdot \left(\dfrac{1}ε\right)^{o\left(k^{1-1/d}\right)} \cdot n^{o\left(k^{1-1/d}\right)}$ 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\left(d\cdot k^{1-1/d}\right)}$ time for discrete $k$-center on $n$ points in $d$-dimensional Euclidean space is asymptotically optimal. Formally, we show that if for some $d\geq 2$ and some computable function $f$, there is an $f(k)\cdot n^{o\left(k^{1-1/d}\right)}$ 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]
