On the Complexity of Scheduling in Wireless Networks
The authors consider the problem of throughput-optimal scheduling in wireless networks subject to interference constraints. They model the interference using a family of K-hop interference models, under which no two links within a K-hop distance can successfully transmit at the same time. For a given K, they can obtain a throughput-optimal scheduling policy by solving the well-known maximum weighted matching problem. They show that for K > 1, the resulting problems are NP-Hard that cannot be approximated within a factor that grows polynomially with the number of nodes. Interestingly, for geometric unit-disk graphs that can be used to describe a wide range of wireless networks, the problems admit polynomial time approximation schemes within a factor arbitrarily close to 1.