# 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.