Lower bound for multimedia multicast routing

Yiu Wing LEUNG*, B. T. Yang

*Corresponding author for this work

Research output: Contribution to journalJournal articlepeer-review

5 Citations (Scopus)


The optimal multimedia multicast routing problem is to determine a multicast tree of minimal cost to connect a given source node to a given set of destination nodes while fulfilling the delay requirement for multimedia information. This problem has been shown to be NP-complete (Kompella et al., 1993), and hence fast and good heuristic algorithms must be used in practice for a reasonable network size. The authors derive a lower bound on the cost of the optimal multicast trees by Lagrangean relaxation and problem decomposition. The numerical results for some standard test problems demonstrate that the lower bound is very tight and differs from the optimal solutions by only a few percent on average. In addition, the lower bound can be computed quite quickly and the computation time on a SUN workstation is only a few minutes for the networks with 100 nodes. This tight lower bound can be used to evaluate whether any given heuristic algorithm for multimedia multicast routing is close-to-optimal.

Original languageEnglish
Pages (from-to)87-90
Number of pages4
JournalIEE Proceedings: Communications
Issue number2
Publication statusPublished - 1998

Scopus Subject Areas

  • Electrical and Electronic Engineering

User-Defined Keywords

  • Lagrangcan relaxation
  • Lower bounds
  • Multicast trees
  • Multimedia communication
  • Network routing


Dive into the research topics of 'Lower bound for multimedia multicast routing'. Together they form a unique fingerprint.

Cite this