2006 | OriginalPaper | Chapter
On the Hardness of Range Assignment Problems
Author : Bernhard Fuchs
Published in: Algorithms and Complexity
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
We investigate the computational hardness of the
Connectivity
, the
Strong Connectivity
and the
Broadcast
type of Range Assignment Problems in ℝ
2
and ℝ
3
. We present new reductions for the 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
all
real distance-power gradients
α
> 0 (resp.
α
> 1 for
Broadcast
) in 2-d, and prove APX-hardness of all three problems in 3-d for
allα
> 1. Our reductions yield improved lower bounds on the approximation ratios for all problems where APX-hardness was known before already. In particular, we derive the overall first APX-hardness proof for Broadcast. This was an open problem posed in earlier work in this area, as was the question whether (Strong) Connectivity remains NP-hard for
α
= 1. Additionally, we give the first hardness results for so-called well-spread instances.