Exact and approximate link scheduling algorithms under the physical interference model

Abstract

Given n arbitrarily distributed single-hop wireless links, using the physical interference model, the objective is to minimize the scheduling length. This is an open problem (Problem 1) proposed by Locher et al. [21]. In this paper, we solve this open problem at the cost of moderately exponential time. Specifically, this paper gives two classes of exact and approximate link scheduling algorithms, one based on the somewhat straightforward link independent set covering, and the other on counting the number of set covers. Letp(n) denote the time of checking whether the spectral radius of an irreducible non-negative matrix is smaller than 1 or not, then the time complexity for the set covering based exact algorithm isO(2 n/ 2)), whereas the proposed counting based exact scheduling algorithm called ESA-MLSAT needs only time O(3n • n ■ log 2 n ■ p(n)) with polynomial space. If exponential space is allowed, the time complexity can be further reduced to O(2n ■ n ■ log 2 n ■ p(n)). The time complexity for the set covering based approximate algorithm is O(( n n/2)-logn ■ p(n)) with approximation ratio O(logn) . The time complexity of the first counting based approximation algorithm is O(n 2polylog(n)) with approximation ratio O(nlog n), the time complexity of the second counting based approximation algorithm is O(n 1+og3' og n polylog(n)) with approximation ratio O(njlog n), and the time complexity of the third counting based approximate algorithm is O((( n n/2) + 3 e n•n• logn)-logn-p(n)) with approximation ratio |(1 + s)|. All these approximation algorithms use polynomial space. © 2008 ACM.