Approximation and Inapproximability Results for Maximum Clique of Disc Graphs in High Dimensions
| dc.creator | Afshani, Peyman | |
| dc.creator | Hatami, Hamed | |
| dc.date | 2006-12-31 | |
| dc.date | 2009-03-14 | |
| dc.date.accessioned | 2026-07-07T12:52:05Z | |
| dc.date.available | 2026-07-07T12:52:05Z | |
| dc.description | 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 $ε>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}+ε)$. On the hardness side, roughly speaking, we show that unless $P=NP$ for every $ε>0$ it is not possible to guarantee the diameter $r(\sqrt{4/3}-ε)$ for $B$ even if the algorithm is allowed to output a set of size $({95\over 94}-ε)^{-1}|A^*|$. | |
| dc.description | Final version | |
| dc.identifier | https://arxiv.org/abs/cs/0701009 | |
| dc.identifier | http://arxiv.org/abs/cs/0701009 | |
| dc.identifier | Information Processing Letters. 105(3) (2008) pp. 83-87 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/223191 | |
| dc.subject | Computational Geometry | |
| dc.subject | Metric Geometry | |
| dc.title | Approximation and Inapproximability Results for Maximum Clique of Disc Graphs in High Dimensions | |
| dc.type | text |