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{n^2,nΔ^2}) time, improving over a previously known O(n^3) 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.

A.A. Bertossi, M.C. Pinotti, R. Rizzi (2009). Optimal Receiver Scheduling Algorithms for a Multicast Problem. DISCRETE APPLIED MATHEMATICS, 157, 3187-3197 [10.1016/j.dam.2009.06.031].

Optimal Receiver Scheduling Algorithms for a Multicast Problem

BERTOSSI, ALAN ALBERT;
2009

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{n^2,nΔ^2}) time, improving over a previously known O(n^3) 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.
2009
A.A. Bertossi, M.C. Pinotti, R. Rizzi (2009). Optimal Receiver Scheduling Algorithms for a Multicast Problem. DISCRETE APPLIED MATHEMATICS, 157, 3187-3197 [10.1016/j.dam.2009.06.031].
A.A. Bertossi; M.C. Pinotti; R. Rizzi
File in questo prodotto:
Eventuali allegati, non sono esposti

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11585/77945
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? 0
social impact