An Approximation Scheme for Burst Scheduling in Time Slicing Mobile TVs

In this paper, we consider the problem of minimizing switching overhead of burst scheduling in time slicing mobile TV broadcast systems. This problem was formulated by Hsu and Hefeeda, and was given an elegant scheme with approximation ratio of at least two. Our proposed scheme significantly improves the previous scheme. More concretely, it generates a burst schedule for mobile TV systems whose switching overhead is at most (1/ln 2)+ε ≃ 1.4427 times of optimum, where ln is the natural logarithm and epsilon is arbitrary positive constant. Our scheme is a combination of a binary partion of burst cycles and a shifting method which was originally proposed for the analysis of unit disk graphs.