An Efficient Approximation Algorithm for the Steiner Tree Problem

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 eve... View More