Premium
Lower bounds for the relative greedy algorithm for approximating Steiner trees
Author(s) -
Hougardy Stefan,
Kirchner Stefan
Publication year - 2006
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.20100
Subject(s) - steiner tree problem , combinatorics , mathematics , upper and lower bounds , greedy algorithm , approximation algorithm , time complexity , graph , algorithm , discrete mathematics , mathematical analysis
The Steiner tree problem is to find a shortest subgraph that spans a given set of vertices in a graph. This problem is known to be NP‐hard, and it is well known that a polynomial time 2‐approximation algorithm exists. In 1996, Zelikovsky suggested an approximation algorithm for the Steiner tree problem that is called the relative greedy algorithm. Until now the performance ratio of this algorithm has not been known. Zelikovsky provided 1.694 as an upper bound, and Gröpl, Hougardy, Nierhoff, and Prömel proved that 1.333 is a lower bound. In this article we improve the lower bound for the performance ratio of the relative greedy algorithm to 1.385. © 2006 Wiley Periodicals, Inc. NETWORKS, Vol. 47(2), 111–115 2006