Computational Complexity - Research Seminar
Bodo Manthey (University of Twente): Probabilistic Analysis of Power Assignments
Nov. 5, 2013, 11:15 a.m.
E 1 3, Room 415
A fundamental problem for wireless ad hoc networks is the assignment of suitable
transmission powers to the wireless devices such that the resulting
communication graph is connected and the total transmit power is minimized. Our
goal is a probabilistic analysis of this power assignment (PA) problem.
We prove complete convergence of PA for arbitrary combinations of the dimension
d and the distance-power gradient p. In particular, we prove complete
convergence for the case p>=d. As far as we are aware, complete convergence for
p>d has not been proved yet for any Euclidean functional, and complete
convergence p=d has only been proved for the minimum spanning tree functional.
Furthermore, we prove that the expected approximation ratio of a simple spanning
tree heuristic is strictly less than its worst-case ratio of 2.