An efficient approximation algorithm for the Steiner tree problem

研究成果: Conference contribution

摘要

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.

原文English
主出版物標題ACM International Conference Proceeding Series
發行者Association for Computing Machinery
頁面179-184
頁數6
ISBN(列印)9781450361033
DOIs
出版狀態Published - 2019 一月 1
事件2nd International Conference on Information Science and System, ICISS 2019 - Tokyo, Japan
持續時間: 2019 三月 162019 三月 19

出版系列

名字ACM International Conference Proceeding Series
Part F148384

Conference

Conference2nd International Conference on Information Science and System, ICISS 2019
國家Japan
城市Tokyo
期間19-03-1619-03-19

指紋

Approximation algorithms
Computational complexity
Costs

All Science Journal Classification (ASJC) codes

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

引用此文

Chen, C-Y. (2019). An efficient approximation algorithm for the Steiner tree problem. 於 ACM International Conference Proceeding Series (頁 179-184). (ACM International Conference Proceeding Series; 卷 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. 頁 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. 於 ACM International Conference Proceeding Series. ACM International Conference Proceeding Series, 卷 Part F148384, Association for Computing Machinery, 頁 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; 卷 Part F148384).

研究成果: Conference 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. 於 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