×

An optimization problem related to VoD broadcasting. (English) Zbl 1173.90350

Deng, Xiaotie (ed.) et al., Algorithms and computation. 16th international symposium, ISAAC 2005, Sanya, Hainan, China, December 19–21, 2005. Proceedings. Berlin: Springer (ISBN 3-540-30935-7/pbk). Lecture Notes in Computer Science 3827, 116-125 (2005).
Summary: Consider a tree \(T\) of depth 2 whose root has \(s\) child nodes and the \(k^{\text{th}}\) child node from left has \(n_{k}\) child leaves. Considered as a round-robin tree, \(T\) represents a schedule in which each page assigned to a leaf under node \(k\) (\(1 \leq k \leq s\)) appears with period \(sn_k\). By varying \(s\), we want to maximize the total number \(n = \sum_{k =1}^{s} n_k\) of pages assigned to the leaves with the following constraints: for \(1 \leq k \leq s\), \(n_k = \lfloor(m + \sum_{j=1}^{k-1} n_j)/s\rfloor\), where \(m\) is a given integer parameter. This problem arises in the optimization of a video-on-demand scheme, called Fixed-Delay Pagoda Broadcasting.
Due to the floor functions involved, the only known algorithm for finding the optimal \(s\) is essentially exhaustive, testing \(m/2\) different potential optimal values of size \(O(m)\) for \(s\). Since computing \(n\) for a given value of \(s\) incurs time \(O(s)\), the time complexity of finding the optimal \(s\) is \(O(m^2)\). This paper analyzes this combinatorial optimization problem in detail and limits the search space for the optimal \(s\) down to \(\kappa\sqrt m\) different values of size \(O(\sqrt m)\) each, where \(\kappa \approx 0.9\), thus improving the time complexity down to \(O(m)\).
For the entire collection see [Zbl 1098.68001].

MSC:

90B18 Communication networks in operations research
90C90 Applications of mathematical programming
PDFBibTeX XMLCite
Full Text: DOI