6533b7d2fe1ef96bd125e12e

RESEARCH PRODUCT

On the approximability of the range assignment problem on radio networks in presence of selfish agents

Gianluca RossiAndrea E. F. ClementiChristoph AmbühlRiccardo SilvestriPaolo Penna

subject

Mathematical optimizationGeneral Computer ScienceSettore INF/01 - Informaticabusiness.industryWireless networkApproximation algorithmContext (language use)Approximation algorithmsTheoretical Computer ScienceNetwork managementAlgorithmic mechanism design; Energy consumption in wireless networks; Approximation algorithmsEnergy consumption in wireless networksalgorithmic mechanism design; approximation algorithms; energy consumption in wireless networksbusinessTime complexityAssignment problemAlgorithmConnectivityAlgorithmic mechanism designAlgorithmic mechanism designMathematicsComputer Science(all)

description

AbstractWe 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 overall power 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.

yearjournalcountryeditionlanguage
2005-10-01Theoretical Computer Science
10.1016/j.tcs.2005.05.006http://dx.doi.org/10.1016/j.tcs.2005.05.006