Scheduling multicasts on unit-capacity trees and meshes

• Published in: Proceedings of the 1999 10th Annual ACM-SIAM Symposium on Discrete Algorithms, p. 438-447
• SIAM, 1999

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 online 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, where n is the number of nodes in the graph. 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 and there exists a polylogarithmic lower bound on the competitive ratio of any online algorithm on tree topologies. We prove the same lower bound for meshess.

Keywords: Algorithms ; Approximation theory ; Computational complexity ; Congestion control (communication) ; Electric network topology ; Mathematical models ; Telecommunication networks ; Telecommunication traffic ; Trees (mathematics) ; Multicast routing ; Polylogarithmic-competitive algorithm ; Multicasting

Reference

• LTAA-CONF-1999-001
• View record in Scopus

Record created on 2007-01-18, modified on 2016-08-08