Tuesday, 13:45 - 14:10 h, Room: MA 041


Eyjolfur Asgeirsson
Performance of distributed game theoretic algorithms for single slot scheduling in wireless networks

Coauthor: Pradipta Mitra


We consider the capacity problem in wireless networks where the goal is to maximize the number of successful connections in arbitrary wireless networks where a transmission is successful only if the signal-to-interference-plus-noise ratio at the receiver is greater than some threshold. We study a game theoretic approach towards capacity maximization introduced by Andrews and Dinitz, where the key to the approximation is the use of low-regret algorithms. We prove vastly improved bounds for the game theoretic algorithm. In doing so, we achieve the first distributed constant factor approximation algorithm for capacity maximization for the uniform power assignment. When compared to the optimum where links may use an arbitrary power assignment, we prove a O(log Δ) approximation, where Δ is the ratio between the largest and the smallest link in the network. This is an exponential improvement of the approximation factor compared to existing results for distributed algorithms. All our results work for links located in any metric space. In addition, we provide simulation studies clarifying the picture on distributed algorithms for capacity maximization.


Talk 2 of the invited session Tue.2.MA 041
"Practical implementations and models using approximation algorithms" [...]
Cluster 1
"Approximation & online algorithms" [...]


  There are three major facts that should be watched out for in all payday loans in the United States. But it is worth noting that these tests were carried out on the blood cells. Therefore, it's too early to say about scientific evidence of Viagra No RX influence on blood clots.