APPROXIMATION ALGORITHMS FOR TWO KINDS OF STEINER PROBLEMS

Abstract Approximation algorithms for the Steiner Problem in graphs and the rectilinear Steiner problem are presented respectively. These algorithms are not based on constructing the resulting tree step by step. Instead, they get an initial tree at first by a simple way and then concentrate on thoroughly refining it by a loop modification approach. Limitations of aiming at local optimization can be avoided. The results are near global optimum and the algorithms are of low time and space complexity.