Limitations of current wireless link scheduling algorithms

Magnús M. Halldórsson, Christian Konrad, Tigran Tonoyan*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)


We consider the following basic scheduling problem in wireless networks: partition a given set of unit demand communication links into the minimum number of feasible subsets. A subset is feasible if all communications can be done simultaneously, subject to mutual interference. We use the so-called physical model to formulate feasibility. We consider the two families of approximation algorithms that are known to guarantee O(log⁡n) approximation for the scheduling problem, where n is the number of links. We present network constructions showing that the approximation ratios of those algorithms are no better than logarithmic, both in n and in Δ, where Δ is a geometric parameter – the ratio of the maximum and minimum link lengths.

Original languageEnglish
Pages (from-to)154-165
Number of pages12
JournalTheoretical Computer Science
Publication statusPublished - 6 Nov 2020

Bibliographical note

Funding Information:
This work is supported by Icelandic Research Fund grants 120032011 , 152679-051 , and 174484-051 .

Publisher Copyright:
© 2020 Elsevier B.V.

Other keywords

  • Link scheduling
  • Lower bound
  • Wireless network


Dive into the research topics of 'Limitations of current wireless link scheduling algorithms'. Together they form a unique fingerprint.

Cite this