Steiner Tree 1.39 Approximation

# Problem definition.

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).

# Solution

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

#include "test/test_utils/sample_graph.hpp"
#include <iostream>
#include <vector>
int main() {
using SGM = sample_graphs_metrics;
auto metric = SGM::get_graph_metric_steiner();
std::vector<int> terminals = {SGM::A, SGM::B, SGM::C, SGM::D};
std::vector<int> nonterminals = {SGM::E};
std::vector<int> selected_nonterminals;
// solve it
nonterminals, std::back_inserter(selected_nonterminals));
// print result
std::cout << "Selected vertices:" << std::endl;
for (auto v : terminals) {
std::cout << v << std::endl;
}
for (auto v : selected_nonterminals) {
std::cout << v << std::endl;
}
auto cost = paal::ir::steiner_utils::count_cost(selected_nonterminals,
terminals, metric);
std::cout << "Cost of the solution: " << cost << std::endl;
paal::lp::glp::free_env();
}

example file is in steiner_tree_ir_example.cpp

# Approximation Ratio

The approximation ratio for this algorithm equals 1.39

# References

The algorithm is described in the [4].