On the Hardness of Range Assignment Problems
Fuchs, Bernhard
(2006)
On the Hardness of Range Assignment Problems.
Published In:
Algorithms and Complexity : 6th Italian Conference, CIAC 2006, Rome, Italy, May 29-31, 2006. Proceedings, Lecture notes in computer science. 3998 Springer 2006, pp. 127-138.
Abstract
We investigate the computational hardness of the Connectivity, the Strong Connectivity and the Broadcast type of Range Assignment Problems in R^2 and R^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 alpha > 0 (resp. alpha > 1 for 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 Broadcast. This was an open problem posed in earlier work in this area, as was the question whether (Strong) Connectivity remains NP-hard for alpha = 1 . Additionally, we give the first hardness results for so-called well-spread instances.
Download: |
Download (540kB) | Preview |
---|---|
Download: |
Download (420kB) | Preview |
Editorial actions: | ![]() |
Item Type: | Proceedings article |
---|---|
Citations: | 9 (Google Scholar) | 0 (Web of Science) |
Uncontrolled Keywords: | wireless networks computational complexity hardness of approximation |
Subjects: |
|
Divisions: | Institute of Computer Science > Computer Science Department - Prof. Dr. Schrader Mathematical Institute > Prof. Dr. Faigle |
Related URLs: |
ZAIK Number: | zaik2005-488 |
---|---|
Depositing User: | Bernhard Fuchs |
Date Deposited: | 16 Sep 2005 00:00 |
Last Modified: | 19 Dec 2011 09:44 |
URI: | http://e-archive.informatik.uni-koeln.de/id/eprint/488 |