2026-07-22T18:45:17Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:7422 2024-03-06T10:40:33Z ddc:004 open_access

Universal Framework for Wireless Scheduling Problems Ásgeirsson, Eyjólfur I. Halldórsson, Magnús M. Tonoyan, Tigran Wireless Scheduling Physical Model Approximation framework 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Eyjólfur I. Ásgeirsson and Magnús M. Halldórsson and Tigran Tonoyan 2017 Is Part Of LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2017.129 urn:nbn:de:0030-drops-74228 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2017.129 eng https://creativecommons.org/licenses/by/3.0/legalcode