TY - GEN
T1 - An efficient approximation algorithm for the Steiner tree problem
AU - Chen, Chi Yeh
N1 - Funding Information:
The work was supported by the Ministry of Science and Technology, Taiwan, under Grant no. MOST 107-2221-E- 006 - 090 -.
Publisher Copyright:
© 2019 Association for Computing Machinery.
PY - 2019
Y1 - 2019
N2 - The Steiner tree problem is one of the classic and most fundamental NP-hard problems: given an arbitrary weighted graph, seek a minimum-cost tree spanning a given subset of the vertices (terminals). Byrka et al. proposed a 1.3863+ - approximation algorithm in which the linear program is solved at every iteration after contracting a component. Goemans et al. shown that it is possible to achieve the same approximation guarantee while only solving hypergraphic LP relaxation once. However, optimizing hypergraphic LP relaxation exactly is strongly NP-hard. This article presents an efficient two-phase heuristic in greedy strategy that achieves an approximation ratio of 1.4295.
AB - The Steiner tree problem is one of the classic and most fundamental NP-hard problems: given an arbitrary weighted graph, seek a minimum-cost tree spanning a given subset of the vertices (terminals). Byrka et al. proposed a 1.3863+ - approximation algorithm in which the linear program is solved at every iteration after contracting a component. Goemans et al. shown that it is possible to achieve the same approximation guarantee while only solving hypergraphic LP relaxation once. However, optimizing hypergraphic LP relaxation exactly is strongly NP-hard. This article presents an efficient two-phase heuristic in greedy strategy that achieves an approximation ratio of 1.4295.
UR - http://www.scopus.com/inward/record.url?scp=85066925452&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85066925452&partnerID=8YFLogxK
U2 - 10.1145/3322645.3322649
DO - 10.1145/3322645.3322649
M3 - Conference contribution
AN - SCOPUS:85066925452
SN - 9781450361033
T3 - ACM International Conference Proceeding Series
SP - 179
EP - 184
BT - ACM International Conference Proceeding Series
PB - Association for Computing Machinery
T2 - 2nd International Conference on Information Science and System, ICISS 2019
Y2 - 16 March 2019 through 19 March 2019
ER -