## Abstract

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(logn) 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 language | English |
---|---|

Pages (from-to) | 154-165 |

Number of pages | 12 |

Journal | Theoretical Computer Science |

Volume | 840 |

DOIs | |

Publication status | Published - 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