### 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 language | English |
---|---|

Title of host publication | Complexity and Approximation - In Memory of Ker-I Ko |

Editors | Ding-Zhu Du, Jie Wang |

Publisher | Springer |

Pages | 238-251 |

Number of pages | 14 |

ISBN (Print) | 9783030416713 |

DOIs | |

Publication status | Published - 2020 Jan 1 |

Event | International Workshop on Complexity and Approximation, 2019 - Qingdao, China Duration: 2019 Apr 27 → 2019 Apr 28 |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 12000 LNCS |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Conference

Conference | International Workshop on Complexity and Approximation, 2019 |
---|---|

Country | China |

City | Qingdao |

Period | 19-04-27 → 19-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