NDLI: Improved Approximation Algorithms for the Quality of Service Multicast Tree Problem

Content Provider	Springer Nature Link
Author	Karpinski, Marek Mandoiu, Ion I. Olshevsky, Alexander Zelikovsky, Alexander
Copyright Year	2005
Abstract	The Quality of Service Multicast Tree Problem is a generalization of the Steiner tree problem which appears in the context of multimedia multicast and network design. In this generalization, each node possesses a rate and the cost of an edge with length l in a Steiner tree T connecting the source to non-zero rate nodes is l · re, where re is the maximum node rate in the component of T-{e} that does not contain the source. The best previously known approximation ratios for this problem (based on the best known approximation factor of 1.549 for the Steiner tree problem in networks) are 2.066 for the case of two non-zero rates and 4.212 for the case of an unbounded number of rates. In this paper we give improved approximation algorithms with ratios of 1.960 and 3.802, respectively. When the minimum spanning tree heuristic is used for finding approximate Steiner trees, then the previously best known approximation ratios of 2.667 for two non-zero rates and 5.542 for an unbounded number of rates are reduced to 2.414 and 4.311, respectively.
Starting Page	109
Ending Page	120
Page Count	12
File Format	PDF
ISSN	01784617
Journal	Algorithmica
Volume Number	42
Issue Number	2
e-ISSN	14320541
Language	English
Publisher	Springer-Verlag
Publisher Date	2005-03-02
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Algorithm Analysis and Problem Complexity Theory of Computation Mathematics of Computing Algorithms Computer Systems Organization and Communication Networks Data Structures, Cryptology and Information Theory
Content Type	Text
Resource Type	Article
Subject	Applied Mathematics Computer Science Applications

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Better Approximation Algorithms for the Maximum Internal Spanning Tree Problem

An Approximation Algorithm for the Directed Telephone Multicast Problem

Multi-rooted Greedy Approximation of Directed Steiner Trees with Applications

Approximation Algorithms for Quickest Spanning Tree Problems

Improved Approximation Algorithms for Projection Games

Improved Approximation Algorithms for Data Migration

Improved Approximation Algorithms for the Average-Case Tree Searching Problem

Improved Approximation Algorithms for the Min-max Tree Cover and Bounded Tree Cover Problems

Improved Approximation Algorithms for the Spanning Star Forest Problem

Improved Approximation Algorithms for the Quality of Service Multicast Tree Problem

Similar Documents

Better Approximation Algorithms for the Maximum Internal Spanning Tree Problem

An Approximation Algorithm for the Directed Telephone Multicast Problem

Multi-rooted Greedy Approximation of Directed Steiner Trees with Applications

Approximation Algorithms for Quickest Spanning Tree Problems

Improved Approximation Algorithms for Projection Games

Improved Approximation Algorithms for Data Migration

Improved Approximation Algorithms for the Average-Case Tree Searching Problem

Improved Approximation Algorithms for the Min-max Tree Cover and Bounded Tree Cover Problems

Improved Approximation Algorithms for the Spanning Star Forest Problem

Improved Approximation Algorithms for the Quality of Service Multicast Tree Problem