An efficient approximation algorithm for the Steiner tree problem

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

Abstract

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.

Original languageEnglish
Title of host publicationACM International Conference Proceeding Series
PublisherAssociation for Computing Machinery
Pages179-184
Number of pages6
ISBN (Print)9781450361033
DOIs
Publication statusPublished - 2019 Jan 1
Event2nd International Conference on Information Science and System, ICISS 2019 - Tokyo, Japan
Duration: 2019 Mar 162019 Mar 19

Publication series

NameACM International Conference Proceeding Series
VolumePart F148384

Conference

Conference2nd International Conference on Information Science and System, ICISS 2019
CountryJapan
CityTokyo
Period19-03-1619-03-19

Fingerprint

Approximation algorithms
Computational complexity
Costs

All Science Journal Classification (ASJC) codes

  • Software
  • Human-Computer Interaction
  • Computer Vision and Pattern Recognition
  • Computer Networks and Communications

Cite this

Chen, C-Y. (2019). An efficient approximation algorithm for the Steiner tree problem. In ACM International Conference Proceeding Series (pp. 179-184). (ACM International Conference Proceeding Series; Vol. Part F148384). Association for Computing Machinery. https://doi.org/10.1145/3322645.3322649
Chen, Chi-Yeh. / An efficient approximation algorithm for the Steiner tree problem. ACM International Conference Proceeding Series. Association for Computing Machinery, 2019. pp. 179-184 (ACM International Conference Proceeding Series).
@inproceedings{28a388e6dc374bb5ba1508948147eede,
title = "An efficient approximation algorithm for the Steiner tree problem",
abstract = "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.",
author = "Chi-Yeh Chen",
year = "2019",
month = "1",
day = "1",
doi = "10.1145/3322645.3322649",
language = "English",
isbn = "9781450361033",
series = "ACM International Conference Proceeding Series",
publisher = "Association for Computing Machinery",
pages = "179--184",
booktitle = "ACM International Conference Proceeding Series",

}

Chen, C-Y 2019, An efficient approximation algorithm for the Steiner tree problem. in ACM International Conference Proceeding Series. ACM International Conference Proceeding Series, vol. Part F148384, Association for Computing Machinery, pp. 179-184, 2nd International Conference on Information Science and System, ICISS 2019, Tokyo, Japan, 19-03-16. https://doi.org/10.1145/3322645.3322649

An efficient approximation algorithm for the Steiner tree problem. / Chen, Chi-Yeh.

ACM International Conference Proceeding Series. Association for Computing Machinery, 2019. p. 179-184 (ACM International Conference Proceeding Series; Vol. Part F148384).

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

TY - GEN

T1 - An efficient approximation algorithm for the Steiner tree problem

AU - Chen, Chi-Yeh

PY - 2019/1/1

Y1 - 2019/1/1

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

ER -

Chen C-Y. An efficient approximation algorithm for the Steiner tree problem. In ACM International Conference Proceeding Series. Association for Computing Machinery. 2019. p. 179-184. (ACM International Conference Proceeding Series). https://doi.org/10.1145/3322645.3322649