### Abstract

The input in the Group-Steiner Problem consists of an undirected connected graph with a cost function p(e) over the edges and a collection of subsets of vertices {gi} Each subset gi is called a group and the vertices in Ugi are called terminals. The goal is to find a minimum cost tree that contains at least one terminal from every group. We give the first combinatorial polylogarith-mic ratio approximation for the problem on trees. Let m denote the number of groups and S denote the number of terminals. The approximation ratio of our algorithm is O(logS · log m/log log S) = O(log^{2}n/loglogn). This is an improvement by a φ(log log n) factor over the previously best known ap proximation ratio for the Group Steiner Problem on trees [GKR98]. Our result carries over to the Group Steiner Problem on general graphs and to the Covering Steiner Problem. Garg et al. [GKR98] presented a reduction of the Group Steiner Problem on general graphs to trees. Their reduction employs Bar-tal's [B98] approximation of graph metrics by tree metrics. Our algorithm on trees implies an approximation algorithm of ratio O(logS · logm · logn · log log n/ log log S) = O(log^{3} n) for the Group Steiner Problem on general graphs. The previously best known approximation ratio for this problem on general graphs, as a function of n, is O(log^{3}n · log logn) [GKR98]. Our algorithm in conjunction with ideas of [EKS01] gives an O(logS · logm· logn· log logn/ log log S) = O(log^{3} n)-approximation ratio for the more general Covering Steiner Problem, improving the best known approximation ratio (as a function of n) for the Covering Steiner Problem by a Φ(loglogn) factor.

Original language | English (US) |
---|---|

Title of host publication | Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2002 |

Publisher | Association for Computing Machinery |

Pages | 49-58 |

Number of pages | 10 |

ISBN (Electronic) | 089871513X |

State | Published - Jan 1 2002 |

Event | 13th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2002 - San Francisco, United States Duration: Jan 6 2002 → Jan 8 2002 |

### Publication series

Name | Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms |
---|---|

Volume | 06-08-January-2002 |

### Other

Other | 13th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2002 |
---|---|

Country | United States |

City | San Francisco |

Period | 1/6/02 → 1/8/02 |

### Fingerprint

### All Science Journal Classification (ASJC) codes

- Software
- Mathematics(all)

### Cite this

*Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2002*(pp. 49-58). (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms; Vol. 06-08-January-2002). Association for Computing Machinery.

}

*Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2002.*Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, vol. 06-08-January-2002, Association for Computing Machinery, pp. 49-58, 13th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2002, San Francisco, United States, 1/6/02.

**An approximation algorithm for the Group Steiner Problem.** / Even, Guy; Kortsarz, Guy.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - An approximation algorithm for the Group Steiner Problem

AU - Even, Guy

AU - Kortsarz, Guy

PY - 2002/1/1

Y1 - 2002/1/1

N2 - The input in the Group-Steiner Problem consists of an undirected connected graph with a cost function p(e) over the edges and a collection of subsets of vertices {gi} Each subset gi is called a group and the vertices in Ugi are called terminals. The goal is to find a minimum cost tree that contains at least one terminal from every group. We give the first combinatorial polylogarith-mic ratio approximation for the problem on trees. Let m denote the number of groups and S denote the number of terminals. The approximation ratio of our algorithm is O(logS · log m/log log S) = O(log2n/loglogn). This is an improvement by a φ(log log n) factor over the previously best known ap proximation ratio for the Group Steiner Problem on trees [GKR98]. Our result carries over to the Group Steiner Problem on general graphs and to the Covering Steiner Problem. Garg et al. [GKR98] presented a reduction of the Group Steiner Problem on general graphs to trees. Their reduction employs Bar-tal's [B98] approximation of graph metrics by tree metrics. Our algorithm on trees implies an approximation algorithm of ratio O(logS · logm · logn · log log n/ log log S) = O(log3 n) for the Group Steiner Problem on general graphs. The previously best known approximation ratio for this problem on general graphs, as a function of n, is O(log3n · log logn) [GKR98]. Our algorithm in conjunction with ideas of [EKS01] gives an O(logS · logm· logn· log logn/ log log S) = O(log3 n)-approximation ratio for the more general Covering Steiner Problem, improving the best known approximation ratio (as a function of n) for the Covering Steiner Problem by a Φ(loglogn) factor.

AB - The input in the Group-Steiner Problem consists of an undirected connected graph with a cost function p(e) over the edges and a collection of subsets of vertices {gi} Each subset gi is called a group and the vertices in Ugi are called terminals. The goal is to find a minimum cost tree that contains at least one terminal from every group. We give the first combinatorial polylogarith-mic ratio approximation for the problem on trees. Let m denote the number of groups and S denote the number of terminals. The approximation ratio of our algorithm is O(logS · log m/log log S) = O(log2n/loglogn). This is an improvement by a φ(log log n) factor over the previously best known ap proximation ratio for the Group Steiner Problem on trees [GKR98]. Our result carries over to the Group Steiner Problem on general graphs and to the Covering Steiner Problem. Garg et al. [GKR98] presented a reduction of the Group Steiner Problem on general graphs to trees. Their reduction employs Bar-tal's [B98] approximation of graph metrics by tree metrics. Our algorithm on trees implies an approximation algorithm of ratio O(logS · logm · logn · log log n/ log log S) = O(log3 n) for the Group Steiner Problem on general graphs. The previously best known approximation ratio for this problem on general graphs, as a function of n, is O(log3n · log logn) [GKR98]. Our algorithm in conjunction with ideas of [EKS01] gives an O(logS · logm· logn· log logn/ log log S) = O(log3 n)-approximation ratio for the more general Covering Steiner Problem, improving the best known approximation ratio (as a function of n) for the Covering Steiner Problem by a Φ(loglogn) factor.

UR - http://www.scopus.com/inward/record.url?scp=26444605118&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=26444605118&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:26444605118

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 49

EP - 58

BT - Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2002

PB - Association for Computing Machinery

ER -