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

    指紋

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