Bandwidth maximization in multicasting

Garg, Naveen ; Khandekar, Rohit ; Kunal, Keshav ; Pandit, Vinayaka (2003) Bandwidth maximization in multicasting In: 11th Annual European Symposium, September 16-19, 2003, Budapest, Hungary.

Full text not available from this repository.

Official URL:


We formulate bandwidth maximization problems in multicasting streaming data. Multicasting is used to stream data to many terminals simultaneously. The goal here is to maximize the bandwidth at which the data can be transmitted satisfying the capacity constraints on the links. A typical network consists of the end-hosts which are capable of duplicating data instantaneously and the routers which can only forward the data. We show that if one insists that all the data to a terminal should travel along a single path, then it is NP-hard to approximate the maximum bandwidth to a factor better than 2. We also present a fast 2-approximation algorithm. If different parts of the data to a terminal can travel along different paths, the problem can be approximated to the same factor as the minimum Steiner tree problem on undirected graphs. We also prove that in case of a tree network, both versions of the bandwidth maximization problem can be solved optimally in polynomial time. Of independent interest is our result that the minimum Steiner tree problem on tree-metrics can be solved in polynomial time.

Item Type:Conference or Workshop Item (Paper)
Source:Copyright of this article belongs to Springer-Verlag.
ID Code:101315
Deposited On:31 Jan 2018 09:33
Last Modified:31 Jan 2018 09:33

Repository Staff Only: item control page