Computer Science – Computational Geometry
Scientific paper
2006-12-31
Information Processing Letters. 105(3) (2008) pp. 83-87
Computer Science
Computational Geometry
Final version
Scientific paper
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^*|$.
Afshani Peyman
Hatami Hamed
No associations
LandOfFree
Approximation and Inapproximability Results for Maximum Clique of Disc Graphs in High Dimensions does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Approximation and Inapproximability Results for Maximum Clique of Disc Graphs in High Dimensions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Approximation and Inapproximability Results for Maximum Clique of Disc Graphs in High Dimensions will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-293945