In the Steiner tree problem we are given the set of nonterminals, the set of terminals and the metric m. Our goal is to find a minimum cost tree connecting all terminals (it can possibly contain some nonterminal nodes).
This solution implements LP-based approximation algorithm. It is currently the best known approximation algorithm for solving general Steiner Tree problem.
We consider an LP relaxation of the problem, which is based on the notion of directed components. We sample one component with probability proportional to the value of the associated variable in a fractional solution: the sampled component is contracted and the LP is updated consequently. We iterate this process until all terminals are connected.
example file is in steiner_tree_ir_example.cpp
The approximation ratio for this algorithm equals 1.39
The algorithm is described in the .