Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR05-113 | 12th September 2005 00:00

On the Hardness of Range Assignment Problems


Authors: Bernhard Fuchs
Publication: 9th October 2005 04:38
Downloads: 3475


We investigate the computational hardness of the {\sc Connectivity},
the {\sc Strong Connectivity} and the {\sc Broadcast} type of Range
Assignment Problems in $\R^2$ and $\R^3$.
We present new reductions for the {\sc Connectivity} problem, which
are easily adapted to suit the other two problems. All reductions
are considerably simpler than the technically quite involved ones
used in earlier works on these problems. Using our constructions, we
can for the first time prove NP-hardness of these problems for
\emph{all} real distance-power gradients $\alpha > 0$ (resp.\
$\alpha > 1$ for {\sc Broadcast}) in 2-d, and give improved lower
bounds on the approximation ratios of all three problems in 3-d for
all $\alpha > 1$. In particular, we derive the overall first
APX-hardness proof for {\sc Broadcast}. This was an open problem
posed in earlier work in this area, as was the question whether {\sc
(Strong) Connectivity} remains NP-hard for $\alpha = 1$.
Additionally, we give the first hardness results for so-called
well-spread instances.

ISSN 1433-8092 | Imprint