Scheduling multicasts on unit-capacity trees and meshes

Henzinger MH, Leonardi  S. 1999. Scheduling multicasts on unit-capacity trees and meshes. 10th Annual ACM-SIAM Symposium on Discrete Algorithms. SODA: Symposium on Discrete Algorithms, 438–447.

Download
No fulltext has been uploaded. References only!
Conference Paper | 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 NPhard 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)*)-factor approximation algorithm for meshes, where n is the number of nodes in the graph. In the online setting, we give the first polylogarithrnic competitive online algorithm for tree and mesh topologies. No polylogarithmic-competitive algorithm is possible on general network topologies [8] and there exists a polylogarithmic lower bound on the competitive ratio of any online algorithm on tree topologies [l]. We prove the same lower bound for meshes.
Publishing Year
Date Published
1999-01-01
Proceedings Title
10th Annual ACM-SIAM Symposium on Discrete Algorithms
Publisher
Society for Industrial & Applied Mathematics
Page
438-447
Conference
SODA: Symposium on Discrete Algorithms
Conference Location
Baltimore, MD, United States
Conference Date
1999-01-17 – 1999-01-19
ISBN
IST-REx-ID

Cite this

Henzinger MH, Leonardi  S. Scheduling multicasts on unit-capacity trees and meshes. In: 10th Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial & Applied Mathematics; 1999:438-447.
Henzinger, M. H., & Leonardi  , S. (1999). Scheduling multicasts on unit-capacity trees and meshes. In 10th Annual ACM-SIAM Symposium on Discrete Algorithms (pp. 438–447). Baltimore, MD, United States: Society for Industrial & Applied Mathematics.
Henzinger, Monika H, and Stefano Leonardi  . “Scheduling Multicasts on Unit-Capacity Trees and Meshes.” In 10th Annual ACM-SIAM Symposium on Discrete Algorithms, 438–47. Society for Industrial & Applied Mathematics, 1999.
M. H. Henzinger and S. Leonardi  , “Scheduling multicasts on unit-capacity trees and meshes,” in 10th Annual ACM-SIAM Symposium on Discrete Algorithms, Baltimore, MD, United States, 1999, pp. 438–447.
Henzinger MH, Leonardi  S. 1999. Scheduling multicasts on unit-capacity trees and meshes. 10th Annual ACM-SIAM Symposium on Discrete Algorithms. SODA: Symposium on Discrete Algorithms, 438–447.
Henzinger, Monika H., and Stefano Leonardi  . “Scheduling Multicasts on Unit-Capacity Trees and Meshes.” 10th Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial & Applied Mathematics, 1999, pp. 438–47.

Export

Marked Publications

Open Data ISTA Research Explorer

Search this title in

Google Scholar
ISBN Search