Thomas Kesselheim
Abstract:
We design and analyze algorithms managing wireless spectrum accesses from a theoretical perspective, striving for provable performance guarantees. In contrast to most previous studies in algorithmic theory, interference constraints are stated based on the signal-to-interference-plus-noise ratio (SINR). This way, our interference model allows to take power control into account. That is, transmit powers can be individually adjusted in order to minimize the effects of interference.
The starting point of our considerations is the capacity-maximization problem. Given a set of possible communication requests, the task is to select a maximum subset of these requests and a power assignment such that all transmissions can be performed simultaneously. We present the first constant-factor approximations for this problem.
Based on this result, we are able to obtain approximation algorithms for a number of further, more sophisticated scenarios with respect to spectrum allocation and power control in wireless networks. In many cases, these algorithms are the first to achieve non-trivial worst-case performances.