Approximation and Inapproximability Results for Maximum Clique of Disc Graphs in High Dimensions

Abstract

We prove algorithmic and hardness results for the problem of finding the largest set of a fixed diameter in the Euclidean space. In particular, we prove that if $A^{\ast }$ is the largest subset of diameter $r$ of $n$ points in the Euclidean space, then for every $\epsilon >0$ there exists a polynomial time algorithm that outputs a set $B$ of size at least $|A^{\ast }|$ and of diameter at most $r(\sqrt{2}+\epsilon )$. On the hardness side, roughly speaking, we show that unless $P=NP$ for every $\epsilon >0$ it is not possible to guarantee the diameter $r(\sqrt{4/3}-\epsilon )$ for $B$ even if the algorithm is allowed to output a set of size $(\frac{95}{94}-\epsilon {)}^{-1}|A^{\ast }|$.

Final version