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 "paal/iterative_rounding/steiner_tree/steiner_tree.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

Approximation Ratio

The approximation ratio for this algorithm equals 1.39

References

The algorithm is described in the [4].

See Also

• Steiner Tree 11/6 Approximation
• Steiner Tree Dreyfus Wagner
• Steiner Tree Greedy