A polylogarithmic approximation algorithm for the group Steiner tree problem

By Naveen Garg, Goran Konjevod, R. Ravi. ACM-SIAM Symposium on Discrete Algorithms, 2000

392 citations recorded by the source corpus.

Subfields: Computational Theory and Mathematics, Computer Graphics and Computer-Aided Design

View Paper: https://www.semanticscholar.org/paper/43b39ed60cda5e724c073d8f98074cd93ceb5c85

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

1. Jeffrey Xu Yu
2. Satish Rao
3. Lu Qin
4. Carlos Castillo
5. Aristides Gionis
6. Bolin Ding
7. Jittat Fakcharoenphol
8. Luca Becchetti

In Computer Graphics and Computer-Aided Design

1. Satish Rao
2. Jittat Fakcharoenphol
3. Kunal Talwar

Citations in the corpus

• Online team formation in social networks (2012, background): “This constraint, along with the coverage constraint cov ( J , q ) = 1, define a group Steiner tree problem [6, 10].”
• A tight bound on approximating arbitrary metrics by tree metrics (2003, methodology): “This gives improved approximation algorithms for various problems including group Steiner tree [24], metric labeling [19, 32], buy-at-bulk network design [4], and vehicle routing [16].”
• Finding Top-k Min-Cost Connected Trees in Databases (2007, background): “We do not compare our results with the work in [19, 5, 16, 8, 9, 15], because their time complexity is higher than O(n(2)), which make them difficult to handle large database graphs.”