• search hit 21 of 28
Back to Result List

Lower Bounds for the Relative Greedy Algorithm for Approximating Steiner Trees

Please always quote using this URN:urn:nbn:de:0296-matheon-2827
  • The Steiner tree problem is to nd 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 [11] suggested an approximation algorithm for the Steiner tree problem that is called the relative greedy algorithm. Till today the performance ratio of this algorithm is not known. Zelikovsky provided 1.694 as an upper bound and Gröpl, Hougardy, Nierho and Prömel [6] proved that 1.333 is a lower bound. In this paper we improve the lower bound for the performance ratio of the relative greedy algorithm to 1.385.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Metadaten
Author:Stefan Hougardy, Stefan Kirchner
URN:urn:nbn:de:0296-matheon-2827
Referee:Hans Jürgen Prömel
Document Type:Preprint, Research Center Matheon
Language:English
Date of first Publication:2005/05/11
Release Date:2005/10/31
Institute:Humboldt-Universität zu Berlin
Preprint Number:274
Verstanden ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.