An efficient approximation algorithm for the steiner tree problem

研究成果: Conference contribution

1 引文 斯高帕斯(Scopus)

摘要

Given an arbitrary weighted graph, the Steiner tree problem seeks a minimum-cost tree spanning a given subset of the vertices (terminals). Byrka et al. proposed an interactive method that achieves an approximation ratio of 1.3863+ϵ. Moreover, Goemans et al. shown that it is possible to achieve the same approximation guarantee while only solving hypergraphic LP relaxation once. However, solving hypergraphic LP relaxation is time consuming. This article presents an efficient two-phase heuristic in greedy strategy that achieves an approximation ratio of 1.4295.

原文English
主出版物標題Complexity and Approximation - In Memory of Ker-I Ko
編輯Ding-Zhu Du, Jie Wang
發行者Springer
頁面238-251
頁數14
ISBN(列印)9783030416713
DOIs
出版狀態Published - 2020 一月 1
事件International Workshop on Complexity and Approximation, 2019 - Qingdao, China
持續時間: 2019 四月 272019 四月 28

出版系列

名字Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
12000 LNCS
ISSN(列印)0302-9743
ISSN(電子)1611-3349

Conference

ConferenceInternational Workshop on Complexity and Approximation, 2019
國家China
城市Qingdao
期間19-04-2719-04-28

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

指紋 深入研究「An efficient approximation algorithm for the steiner tree problem」主題。共同形成了獨特的指紋。

  • 引用此

    Chen, C. Y., & Hsieh, S. Y. (2020). An efficient approximation algorithm for the steiner tree problem. 於 D-Z. Du, & J. Wang (編輯), Complexity and Approximation - In Memory of Ker-I Ko (頁 238-251). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); 卷 12000 LNCS). Springer. https://doi.org/10.1007/978-3-030-41672-0_15