Scheduling multicasts on unit-capacity trees and meshes

Henzinger MH, Leonardi S. 2003. Scheduling multicasts on unit-capacity trees and meshes. Journal of Computer and System Sciences. 66(3), 567–611.

Download (ext.)

Journal Article | Published | English

Scopus indexed
Author
Henzinger, MonikaISTA ; Leonardi, Stefano
Abstract
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 -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 (Lower bounds for on-line graph problems with application to on-line circuits and optical routing, in: Proceedings of the 28th ACM Symposium on Theory of Computing, 1996, pp. 531–540) and there exists a polylogarithmic lower bound on the competitive ratio of any online algorithm on tree topologies (Making commitments in the face of uncertainity: how to pick a winner almost every time, in: Proceedings of the 28th Annual ACM Symposium on Theory of Computing, 1996, pp. 519–530). We prove the same lower bound for meshes.
Publishing Year
Date Published
2003-05-01
Journal Title
Journal of Computer and System Sciences
Publisher
Elsevier
Volume
66
Issue
3
Page
567-611
ISSN
IST-REx-ID

Cite this

Henzinger MH, Leonardi S. Scheduling multicasts on unit-capacity trees and meshes. Journal of Computer and System Sciences. 2003;66(3):567-611. doi:10.1016/s0022-0000(03)00043-6
Henzinger, M. H., & Leonardi, S. (2003). Scheduling multicasts on unit-capacity trees and meshes. Journal of Computer and System Sciences. Elsevier. https://doi.org/10.1016/s0022-0000(03)00043-6
Henzinger, Monika H, and Stefano Leonardi. “Scheduling Multicasts on Unit-Capacity Trees and Meshes.” Journal of Computer and System Sciences. Elsevier, 2003. https://doi.org/10.1016/s0022-0000(03)00043-6.
M. H. Henzinger and S. Leonardi, “Scheduling multicasts on unit-capacity trees and meshes,” Journal of Computer and System Sciences, vol. 66, no. 3. Elsevier, pp. 567–611, 2003.
Henzinger MH, Leonardi S. 2003. Scheduling multicasts on unit-capacity trees and meshes. Journal of Computer and System Sciences. 66(3), 567–611.
Henzinger, Monika H., and Stefano Leonardi. “Scheduling Multicasts on Unit-Capacity Trees and Meshes.” Journal of Computer and System Sciences, vol. 66, no. 3, Elsevier, 2003, pp. 567–611, doi:10.1016/s0022-0000(03)00043-6.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]

Link(s) to Main File(s)
Access Level
OA Open Access

Export

Marked Publications

Open Data ISTA Research Explorer

Search this title in

Google Scholar