Approximation scheme for burst scheduling with minimum overhead in time slicing mobile TV.

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 approximation scheme with an approximation ratio of at least two. Our proposed scheme significantly improves the approximation ratio of the previous scheme. More concretely, it generates a burst schedule for mobile TV systems whose switching overhead is at most $$(1/\ln 2)+\epsilon \simeq 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 is commonly used for the analysis of approximation algorithms designed for unit disk graphs. [ABSTRACT FROM AUTHOR]

Copyright of Journal of Supercomputing is the property of Springer Nature and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)