Optimal receiver scheduling algorithms for a multicast problem |
| |
Authors: | AA Bertossi MC Pinotti R Rizzi |
| |
Institution: | aDepartment of Computer Science, University of Bologna, Mura Anteo Zamboni, 7, 40127 Bologna, Italy;bDepartment of Computer Science and Mathematics, University of Perugia, Via Vanvitelli, 1, 06123 Perugia, Italy;cDepartment of Mathematics and Computer Science, University of Udine, Via delle Scienze, 208, 33100 Udine, Italy |
| |
Abstract: | This paper studies a multicast problem arising in wavelength division multiplexing single-hop lightwave networks, as well as in Video-on-Demand systems. In this problem, the same message of duration Δ has to be transmitted to a set of n receivers which are not all available simultaneously. The receivers can be partitioned into subsets, each served by a different transmission, with the objective of minimizing their overall waiting cost. When there is a single data channel available for transmission, a dynamic programming algorithm is devised which finds an optimal solution in O(nlogn+min{n2,nΔ2}) time, improving over a previously known O(n3) time algorithm. When multiple data channels are available for transmission, an optimal O(n) time algorithm is proposed which finds an optimal solution if the message has constant transmission duration, whereas an NP-completeness proof is given if the message has arbitrary transmission duration. |
| |
Keywords: | Multicast algorithm Dynamic programming Batch-processing machine scheduling Wavelength division multiplexing lightwave networks Receiver scheduling Video-on-Demand systems |
本文献已被 ScienceDirect 等数据库收录! |
|