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
事件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

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

引用此