Anzeige
Erschienen in:
01.08.2014
Approximation scheme for burst scheduling with minimum overhead in time slicing mobile TV
Erschienen in: The Journal of Supercomputing | Ausgabe 2/2014
EinloggenAktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
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.