Title | ||
---|---|---|
On the approximability of the range assignment problem on radio networks in presence of selfish agents |
Abstract | ||
---|---|---|
We consider the range assignment problem in ad-hoc wireless networks in the context of selfish agents: A network manager aims to assigning transmission ranges to the stations in order to achieve strong connectivity of the network within a minimal overallpower consumption. Station is not directly controlled by the manager and may refuse to transmit with a certain transmission range because it might be costly in terms of power consumption.We investigate the existence of payment schemes which induce the stations to follow the decisions of a network manager in computing a range assignment, that is, truthful mechanisms for the range assignment problem. We provide both positive and negative results on the existence of truthful VCG-based mechanisms for this NP-hard problem. We prove that (i) in general, every polynomial-time truthful VCG-based mechanism computes a solution of cost far-off the optimum, unless P = NP and (ii) there exists a polynomial-time truthful VCG-based mechanism achieving constant approximation for practically relevant, still NP-hard versions, i.e., the metric and the well-spread case. |
Year | DOI | Venue |
---|---|---|
2005 | 10.1016/j.tcs.2005.05.006 | Theor. Comput. Sci. |
Keywords | DocType | Volume |
ad-hoc wireless network,Approximation algorithms,Energy consumption in wireless networks,truthful mechanism,range assignment,selfish agent,polynomial-time truthful VCG-based mechanism,certain transmission range,truthful VCG-based mechanism,network manager,Algorithmic mechanism design,range assignment problem,radio network,NP-hard problem,assigning transmission range | Journal | 343 |
Issue | ISSN | Citations |
1-2 | Theoretical Computer Science | 8 |
PageRank | References | Authors |
0.57 | 11 | 5 |
Name | Order | Citations | PageRank |
---|---|---|---|
Christoph Ambühl | 1 | 357 | 18.50 |
Andrea E. F. Clementi | 2 | 1168 | 85.30 |
Paolo Penna | 3 | 202 | 16.42 |
Gianluca Rossi | 4 | 235 | 21.60 |
Riccardo Silvestri | 5 | 1324 | 90.84 |