Limitations of current wireless link scheduling algorithms

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.