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

All Science Journal Classification (ASJC) codes

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

Fingerprint Dive into the research topics of 'An efficient approximation algorithm for the Steiner tree problem'. Together they form a unique fingerprint.

Cite this