A 1.598 approximation algorithm for the Steiner problem in graphs

Abstract

We present a general iterative framework for improving the performance ratio of Steiner tree approximation algorithms. By applying this framework to one specific algorithm we obtain a new polynomial time approximation algorithm for the Steiner tree problem in graphs that achieves a performance ratio of 1.598 after 11 iterations. This beats the so far best known factor of 1.644 due to Karpinski and Zelikovsky [10]. With the help of a computer program we estimate the limit performance of our algorithm to be 1.588.