2017/09/12 by Chi‐Yeh Chen, Chi-Yeh Chen, Chen, Chi-Yeh · 3 citations
Computer Science · Engineering · Mathematics · #Approximation algorithm #Binary tree #Combinatorics #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #Discrete mathematics #FOS: Computer and information sciences #Formal Methods in Verification #Graph #Greedy algorithm #Heuristic #K-ary tree #Linear programming #Linear programming relaxation #Mathematical optimization #Mathematics #Minimum spanning tree #Relaxation (psychology) #Spanning tree #Steiner tree problem #Tree (set theory) #Tree structure #VLSI and FPGA Design Techniques #cs.DS #k-minimum spanning tree
paper · pdf · doi:10.48550/arxiv.1709.03867
published in arXiv (Cornell University) (Cornell University)
openalex publication_date 2017/09/12 · arxiv created 2018/11/01 · arxiv updated 2018/11/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
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.