An approximation algorithm for the Group Steiner Problem

Guy Even, Guy Kortsarz

Research output: Chapter in Book/Report/Conference proceedingConference contribution

7 Citations (Scopus)

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(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.

Original languageEnglish (US)
Title of host publicationProceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2002
PublisherAssociation for Computing Machinery
Pages49-58
Number of pages10
ISBN (Electronic)089871513X
StatePublished - Jan 1 2002
Event13th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2002 - San Francisco, United States
Duration: Jan 6 2002Jan 8 2002

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
Volume06-08-January-2002

Other

Other13th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2002
CountryUnited States
CitySan Francisco
Period1/6/021/8/02

Fingerprint

Steiner's problem
Approximation algorithms
Approximation Algorithms
Covering Problem
Trees (mathematics)
Cost functions
Approximation
Graph in graph theory
Best Approximation
Denote
Metric Graphs
Subset
Costs
Undirected Graph
Cost Function
Connected graph
Imply
Metric

All Science Journal Classification (ASJC) codes

  • Software
  • Mathematics(all)

Cite this

Even, G., & Kortsarz, G. (2002). An approximation algorithm for the Group Steiner Problem. In 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.
Even, Guy ; Kortsarz, Guy. / An approximation algorithm for the Group Steiner Problem. Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2002. Association for Computing Machinery, 2002. pp. 49-58 (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).
@inproceedings{e1db9a09e3ba48c3a3389a3e01ce541d,
title = "An approximation algorithm for the Group Steiner Problem",
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(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.",
author = "Guy Even and Guy Kortsarz",
year = "2002",
month = "1",
day = "1",
language = "English (US)",
series = "Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms",
publisher = "Association for Computing Machinery",
pages = "49--58",
booktitle = "Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2002",

}

Even, G & Kortsarz, G 2002, An approximation algorithm for the Group Steiner Problem. in 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.

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

Research output: Chapter in Book/Report/Conference proceedingConference 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 -

Even G, Kortsarz G. An approximation algorithm for the Group Steiner Problem. In Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2002. Association for Computing Machinery. 2002. p. 49-58. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).