Approximation Scheme for Burst Scheduling with Minimum Overhead in Time Slicing Mobile TV
Approximation Scheme for Burst Scheduling with Minimum Overhead in Time Slicing Mobile TV
复制标题
时间切片移动电视中最小开销的突发调度近似方案
DOI：
10.1007/s11227-014-1093-1
复制
发表时间：
2014
影响因子：
3.3
通讯作者：
Satoshi Fujita
中科院分区：
文献类型：
--
作者：
Keisuke Kamada;Tohru KONDO;Kouji Nishimura;Reiji Aibara;Satoshi Fujita
在本文中，我们考虑了时间切片移动电视广播系统中突发调度的切换开销最小化的问题。这个问题由 Hsu 和 Hefeeda 提出，并给出了一个优雅的近似方案，近似比至少为 2。我们提出的方案显着提高了先前方案的近似率。更具体地说，它为移动电视系统生成一个突发调度，其切换开销在大多数情况下是最佳的，其中 是自然对数并且是任意正常数。我们的方案是突发周期的二进制部分和移位方法的组合，该方法通常用于分析为单位圆盘图设计的近似算法。
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 mosttimes of optimum, whereis the natural logarithm andis 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.