ECCC-Report TR05-113https://eccc.weizmann.ac.il/report/2005/113Comments and Revisions published for TR05-113en-usSun, 09 Oct 2005 04:38:02 +0200
Paper TR05-113
| On the Hardness of Range Assignment Problems |
Bernhard Fuchs
https://eccc.weizmann.ac.il/report/2005/113We 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.
Sun, 09 Oct 2005 04:38:02 +0200https://eccc.weizmann.ac.il/report/2005/113