A polylogarithmic approximation algorithm for the group Steiner tree problem

被引：165

作者：

Garg, N ^{[1
]}

Konjevod, G

Ravi, R

机构：

[1] Indian Inst Technol, New Delhi 110016, India

[2] Carnegie Mellon Univ, Dept Math Sci, Pittsburgh, PA 15213 USA

[3] Carnegie Mellon Univ, GSIA, Pittsburgh, PA 15213 USA

来源：

JOURNAL OF ALGORITHMS-COGNITION INFORMATICS AND LOGIC | 2000年 / 37卷 / 01期

基金：

美国国家科学基金会;

关键词：

D O I：

10.1006/jagm.2000.1096

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

Given a weighted graph with some subsets of verticcs called groups. the group Steiner tree problem is to find a minimum-weight subgraph which contains at least one vertex from each group. We give a randomized algorithm with a polylogarithmic approximation guarantee for the group Steiner tree problem. The previous best approximation guarantee was O(i(2)k(1/i)) in time O(n(i)k(2i)) (Charikar, Chekuri, Goel. and Guha). Our algorithm also improves existing approximation results fur network design problems with location-based constraints and for the symmetric generalized traveling salesman problem. (C) 2000 Academic Press.

引用

页码：66 / 84

页数：19

共 30 条

[1]

ALON N, 1903, PROBABILISTIC METHOD

[2] Polynomial time approximation schemes for euclidean TSP and other geometric problems [J].

Arora, S .

37TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, PROCEEDINGS, 1996, :2-11

[3]

ARORA S, 1997, P 29 ANN ACM S THEOR, P485

[4]

Bartal Y., 1998, Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing, P161, DOI 10.1145/276698.276725

[5] Probabilistic approximation of metric spaces and its algorithmic applications [J].

Bartal, Y .

37TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, PROCEEDINGS, 1996, :184-193

[6]

BATEMAN CD, 1997, P ACM SIGDA INT S PH

[7]

Charikar M., 1998, PROC 9 ANN ACM SIAM, P192

[8]

CHEW LP, 1989, J COMPUT SYST SCI, V39, P205, DOI 10.1016/0022-0000(89)90044-5

[9] A threshold of in n for approximating set cover [J].

Feige, U .

JOURNAL OF THE ACM, 1998, 45 (04) :634-652

[10] A branch-and-cut algorithm for the symmetric generalized traveling salesman problem [J].

Fischetti, M ;

Gonzalez, JJS ;

Toth, P .

OPERATIONS RESEARCH, 1997, 45 (03) :378-394

← 1 2 3 →