An Efficient Approximation Algorithm for the Steiner Tree Problem

DOI10.1007/978-3-030-41672-0_15MaRDI QIDQ3297834zbMATH OpenOpenAlexFDO

Authors C. Y. Chen, Sun-Yuan Hsieh

Publication date 20 July 2020

Published in Complexity and Approximation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1709.03867

zbMATH Keywords

approximation algorithmsnetwork designSteiner treesgraph Steiner problem

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Abstract: The Steiner tree problem is one of the classic and most fundamental $mathcalNP$-hard problems: given an arbitrary weighted graph, seek a minimum-cost tree spanning a given subset of the vertices (terminals). Byrka emph{et al}. proposed a $1.3863+epsilon$-approximation algorithm in which the linear program is solved at every iteration after contracting a component. Goemans emph{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$.

Recommendations

• On efficient implementation of an approximation algorithm for the Steiner tree problem
• A faster approximation algorithm for the Steiner tree problem in graphs
• scientific article; zbMATH DE number 169458
• scientific article; zbMATH DE number 139910
• scientific article; zbMATH DE number 4063109
• scientific article; zbMATH DE number 1834686
• New approximation algorithms for the Steiner tree problems
• Improved Approximations for the Steiner Tree Problem
• scientific article; zbMATH DE number 742979
• A Faster Algorithm for the Steiner Tree Problem

Cites work

• scientific article; zbMATH DE number 4191148 (Why is no real title available?)
• scientific article; zbMATH DE number 3677874 (Why is no real title available?)
• scientific article; zbMATH DE number 1303564 (Why is no real title available?)
• scientific article; zbMATH DE number 1305435 (Why is no real title available?)
• scientific article; zbMATH DE number 750011 (Why is no real title available?)
• 1.25-Approximation Algorithm for Steiner Tree Problem with Distances 1 and 2
• A note on the terminal Steiner tree problem
• Algorithms for terminal Steiner trees
• An 11/6-approximation algorithm for the network Steiner problem
• Approximation Schemes for Steiner Forest on Planar Graphs and Graphs of Bounded Treewidth
• Improved Approximations for the Steiner Tree Problem
• Improved approximation algorithms for prize-collecting Steiner tree and TSP
• Improving construction for connected dominating set with Steiner tree in wireless sensor networks
• Integrality Ratio for Group Steiner Trees and Directed Steiner Trees
• Matroids and integrality gaps for hypergraphic Steiner tree relaxations
• New Reduction Techniques for the Group Steiner Tree Problem
• New approximation algorithms for the Steiner tree problems
• Node-weighted Steiner tree and group Steiner tree in planar graphs
• On approximation algorithms for the terminal Steiner tree problem
• On the Internal Steiner Tree Problem
• On the equivalence of the bidirected and hypergraphic relaxations for Steiner tree
• On the full and bottleneck full Steiner tree problems
• On the terminal Steiner tree problem.
• Polylogarithmic inapproximability
• Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
• RNC-approximation algorithms for the steiner problem
• Steiner tree approximation via iterative randomized rounding
• The Steiner problem with edge lengths 1 and 2
• The Steiner tree problem
• The Steiner tree problem on graphs: inapproximability results
• The full Steiner tree problem
• The internal Steiner tree problem: Hardness and approximations
• Thek-Steiner Ratio in Graphs
• Tighter Bounds for Graph Steiner Tree Approximation
• When Trees Collide: An Approximation Algorithm for the Generalized Steiner Problem on Networks

Cited in

(14)

• scientific article; zbMATH DE number 1555959 (Why is no real title available?)
• Tighter Bounds for Graph Steiner Tree Approximation
• The Power of Dynamic Distance Oracles
• scientific article; zbMATH DE number 5313630 (Why is no real title available?)
• Efficient Greedy Heuristics For Steiner Tree Problems Using Reolptimization And Super Modularity
• An exact branch and bound algorithm for the Steiner Problem in Graphs
• scientific article; zbMATH DE number 1445376 (Why is no real title available?)
• scientific article; zbMATH DE number 169458 (Why is no real title available?)
• Robust Algorithms for TSP and Steiner Tree
• On efficient implementation of an approximation algorithm for the Steiner tree problem
• An improved algorithm for the Steiner tree problem with bounded edge-length
• An improved LP-based approximation for Steiner tree
• Combination algorithms for Steiner tree variants
• scientific article; zbMATH DE number 6264040 (Why is no real title available?)

This page was built for publication: An Efficient Approximation Algorithm for the Steiner Tree Problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3297834)