1 Search Results for "Ásgeirsson, Eyjólfur I."


Document
Universal Framework for Wireless Scheduling Problems

Authors: Eyjólfur I. Ásgeirsson, Magnús M. Halldórsson, and Tigran Tonoyan

Published in: LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)


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 propose the first framework for approximation algorithms in the physical model that addresses 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 a novel type of amenable conflict graphs, at a small cost. We also show that the approximation obtained is provably the best possible for any conflict graph formulation.

Cite as

Eyjólfur I. Ásgeirsson, Magnús M. Halldórsson, and Tigran Tonoyan. Universal Framework for Wireless Scheduling Problems. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 129:1-129:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)


Copy BibTex To Clipboard

@InProceedings{asgeirsson_et_al:LIPIcs.ICALP.2017.129,
  author =	{\'{A}sgeirsson, Eyj\'{o}lfur I. and Halld\'{o}rsson, Magn\'{u}s M. and Tonoyan, Tigran},
  title =	{{Universal Framework for Wireless Scheduling Problems}},
  booktitle =	{44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)},
  pages =	{129:1--129:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-041-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{80},
  editor =	{Chatzigiannakis, Ioannis and Indyk, Piotr and Kuhn, Fabian and Muscholl, Anca},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2017.129},
  URN =		{urn:nbn:de:0030-drops-74228},
  doi =		{10.4230/LIPIcs.ICALP.2017.129},
  annote =	{Keywords: Wireless, Scheduling, Physical Model, Approximation framework}
}
  • Refine by Author
  • 1 Halldórsson, Magnús M.
  • 1 Tonoyan, Tigran
  • 1 Ásgeirsson, Eyjólfur I.

  • Refine by Classification

  • Refine by Keyword
  • 1 Approximation framework
  • 1 Physical Model
  • 1 Scheduling
  • 1 Wireless

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2017

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail