𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Approximation algorithms for the k-source multicast tree construction problem

✍ Scribed by Paraskevi Fragopoulou

Publisher
John Wiley and Sons
Year
2006
Tongue
English
Weight
155 KB
Volume
47
Category
Article
ISSN
0028-3045

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

A Polylogarithmic Approximation Algorith
A Polylogarithmic Approximation Algorithm for the Group Steiner Tree Problem
✍ Naveen Garg; Goran Konjevod; R. Ravi πŸ“‚ Article πŸ“… 2000 πŸ› Elsevier Science 🌐 English βš– 130 KB

The group Steiner tree problem is a generalization of the Steiner tree problem where we are given several subsets (groups) of vertices in a weighted graph, and the goal is to find a minimum-weight connected subgraph containing at least one vertex from each group.The problem was introduced by Reich a

A Constant-Factor Approximation Algorith
A Constant-Factor Approximation Algorithm for the k-Median Problem
✍ Moses Charikar; Sudipto Guha; Γ‰va Tardos; David B. Shmoys πŸ“‚ Article πŸ“… 2002 πŸ› Elsevier Science 🌐 English βš– 165 KB

We present the first constant-factor approximation algorithm for the metric k-median problem. The k-median problem is one of the most wellstudied clustering problems, i.e., those problems in which the aim is to partition a given set of points into clusters so that the points within a cluster are rel

A New Approximation Algorithm for the St
A New Approximation Algorithm for the Steiner Tree Problem with Performance Ratio 5/3
✍ Hans JΓΌrgen PrΓΆmel; Angelika Steger πŸ“‚ Article πŸ“… 2000 πŸ› Elsevier Science 🌐 English βš– 100 KB

In this paper we present an RNC approximation algorithm for the Steiner tree problem in graphs with performance ratio 5r3 and RNC approximation algorithms for the Steiner tree problem in networks with performance ratio 5r3 q β‘€ for all β‘€ ) 0. This is achieved by considering a related problem, the min