An efficient approximation algorithm for the steiner tree problem

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Citation (Scopus)

Abstract

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.

Original languageEnglish
Title of host publicationComplexity and Approximation - In Memory of Ker-I Ko
EditorsDing-Zhu Du, Jie Wang
PublisherSpringer
Pages238-251
Number of pages14
ISBN (Print)9783030416713
DOIs
Publication statusPublished - 2020 Jan 1
EventInternational Workshop on Complexity and Approximation, 2019 - Qingdao, China
Duration: 2019 Apr 272019 Apr 28

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume12000 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

ConferenceInternational Workshop on Complexity and Approximation, 2019
CountryChina
CityQingdao
Period19-04-2719-04-28

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

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

  • Cite this

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