Approximation of Steiner Minimum Trees in Euclidean Planar Graphs Using Euclidian Steiner Minimum Trees

摘要

Exact solutions for Steiner tree problems in large graphs with large terminal sets cannot be calculated efficiently at the moment. For approximating Steiner minimum trees in large euclidean planar graphs, we propose an algorithm, which uses a solution to the problem in the euclidian plane for initialisation. This is further optimized using stochastic hillclimbing. The algorithm is empirically evaluated with respect to approximation ratio, running time and memory consumption on street networks and compared to an implementation of the Dreyfus Wagner algorithm. The results show, that a SMT can be efficiently approximated in our scenario with an observed average approximation ratio of 1.065 or 1.034 respectively by also using means of local search.