Steiner Tree 1.39 Approximation

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.

#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

paal::ir::steiner_tree_iterative_rounding(metric, terminals,

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

The approximation ratio for this algorithm equals 1.39

The algorithm is described in the [4].

Generated on Tue Jan 31 2017 00:30:52 by 1.8.5