Approximation and Inapproximability Results for Maximum Clique of Disc Graphs in High Dimensions
<|reference_start|>Approximation and Inapproximability Results for Maximum Clique of Disc Graphs in High Dimensions: 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^*$ 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^*|$ 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 $({95\over 94}-\epsilon)^{-1}|A^*|$.<|reference_end|>
@article{afshani2006approximation,
    title={Approximation and Inapproximability Results for Maximum Clique of Disc
  Graphs in High Dimensions},
    author={Peyman Afshani and Hamed Hatami},
    journal={Information Processing Letters. 105(3) (2008) pp. 83-87},
    year={2006},
    archivePrefix={arXiv},
    eprint={cs/0701009},
    primaryClass={cs.CG math.MG}
}