Viðburðir eftir árum


ICE-TCS seminar: Eyjólfur Ingi Ásgeirsson (HR)

  • 25.9.2017, 12:15 - 13:00

ICE-TCS-logo-200pxWhen: Monday the 25th of September at 12:10
Where: M103
Speaker: Eyjólfur Ingi Ásgeirsson (HR)

Title: Universal Framework for Wireless Scheduling Problems

Abstract: An overarching issue in resource management of wireless networks is assessing their capacity: How much communication can be achieved in a network, utilizing all the tools available: power control, scheduling, routing, channel assignment and rate adjustment? We tackle this question in the physical model of interference, and aim for polynomial time algorithms with performance guarantees over arbitrary interference-constrained networks and arbitrary traffic patterns.

We propose the first framework for approximation algorithms that address these questions in full, including rate control. The approximations obtained are doubly logarithmic in the link length and rate diversity. Where previous bounds are known, this gives an exponential improvement.

A key contribution is showing that the complex interference relationship of the physical model can be simplified into novel type of amenable conflict graphs, at a small cost. Besides allowing us to handle a range of scheduling problems, it also has the potential implications for further research on untold resource management questions. The approximation obtained is provably the best possible for any conflict graph formulation.

This work received a best paper award in Track C at the ICALP conference this summer. It is joint work with Magnús Már Halldórsson and Tigran Tonoyan.

We shall not assume any prior background of the audience on distributed or wireless systems.