This paper studies the online Orthogonal Variable Spreading Factor (ovsf) codeassignmentproblem with resource augmentation introduced by Erlebach et al. (in STACS 2004. LNCS, vol. 2996, pp. 270-281, 2004). We propos...
详细信息
This paper studies the online Orthogonal Variable Spreading Factor (ovsf) codeassignmentproblem with resource augmentation introduced by Erlebach et al. (in STACS 2004. LNCS, vol. 2996, pp. 270-281, 2004). We propose a (1 + 1/alpha)-competitive algorithm with help of (1 + left perpendicular alpha right perpendicular) lg*h trees for the height h of the ovsfcode tree and any alpha >= 1. In other words, it is a (1 + epsilon)-competitive algorithm with help of (1 + left perpendicular 1/epsilon right perpendicular)lg*h trees for any constant 0 < epsilon <= 1. In the case of alpha = 1 (or epsilon = 1), we obtain a 2-competitive algorithm with 2 lg* h trees, which substantially improves the previous resource of 3h/8 + 2 trees shown by Chan et al. (COCOON 2009. LNCS, vol. 5609, pp. 358-367, 2009). In another aspect, if it is not necessary to bound the incurred cost for individual requests to a constant, an amortized (4/3+ delta)-competitive algorithm with (11/4 + 4/(3 delta)) trees for any 0 < delta <= 4/3 is also designed in Chan et al. (COCOON 2009. LNCS, vol. 5609, pp. 358-367, 2009). The algorithm in this paper gives us a new trade-off between the competitive ratio and the resource augmentation when alpha >= 3 (or epsilon <= 1/3), although the incurred cost for individual requests is bounded to a constant.
暂无评论