Abstract:
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.