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

We solve this problem using Zelikovsky 11/6 approximation algorithm. The algorithm exploit model of the WeakVoronoi concept (see Voronoi), where the generators are the terminals and the vertices are nonterminals. There is one additional assumption on metric i.e. we only use this metric only for distances (Nonterminal, Terminal) and (Terminal, Terminal).

Example

#include "paal/steiner_tree/zelikovsky_11_per_6.hpp"
#include "test/test_utils/sample_graph.hpp"
#include <iostream>
int main() {
    // sample metric
    typedef sample_graphs_metrics SGM;
    auto gm = SGM::get_graph_metric_steiner();
    typedef decltype(gm) Metric;
    // sample voronoi
    typedef paal::data_structures::voronoi<Metric> voronoiT;
    typedef paal::data_structures::voronoi_traits<voronoiT> VT;
    typedef VT::GeneratorsSet GSet;
    typedef VT::VerticesSet VSet;
    voronoiT voronoi(GSet{ SGM::A, SGM::B, SGM::C, SGM::D }, VSet{ SGM::E },
                     gm);
    // run algorithm
    std::vector<int> steiner_points;
    paal::steiner_tree_zelikovsky11per6approximation(
        gm, voronoi, std::back_inserter(steiner_points));
    // print result
    std::cout << "Steiner points:" << std::endl;
    boost::copy(steiner_points, std::ostream_iterator<int>(std::cout, "\n"));
    return 0;
}

example file is zelikovsky_11_per_6_example.cpp

Approximation Ratio equals 11/6

The complexity

Complexity of the algorithm is \(O(|V|*|E| + |T|^4)\) where T is the set of terminals.

References

The algorithm is described in the [24].