MPI-INF/SWS Research Reports 1991-2021

2. Number - only D1


Scheduling multicasts on unit-capacity trees and meshes

Henzinger, Monika R. and Leonardi, Stefano

May 1998, 38 pages.

Status: available - back from printing

This paper studies the multicast routing and admission control problem on unit-capacity tree and mesh topologies in the throughput-model. The problem is a generalization of the edge-disjoint paths problem and is NP-hard both on trees and meshes. We study both the offline and the online version of the problem: In the offline setting, we give the first constant-factor approximation algorithm for trees, and an O((log log n)^2)-factor approximation algorithm for meshes. In the online setting, we give the first polylogarithmic competitive online algorithm for tree and mesh topologies. No polylogarithmic-competitive algorithm is possible on general network topologies [Bartal,Fiat,Leonardi, 96], and there exists a polylogarithmic lower bound on the competitive ratio of any online algorithm on tree topologies [Awerbuch,Azar,Fiat,Leighton, 96]. We prove the same lower bound for meshes.

  • Attachement: (448 KBytes)

URL to this document:

Hide details for BibTeXBibTeX
  AUTHOR = {Henzinger, Monika R. and Leonardi, Stefano},
  TITLE = {Scheduling multicasts on unit-capacity trees and meshes},
  TYPE = {Research Report},
  INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},
  ADDRESS = {Im Stadtwald, D-66123 Saarbr{\"u}cken, Germany},
  NUMBER = {MPI-I-98-1-015},
  MONTH = {May},
  YEAR = {1998},
  ISSN = {0946-011X},