Repository: Freie Universität Berlin, Math Department

Lower bounds for approximation algorithms for the Steiner tree problem

Gröpl, C. and Hougardy, S. and Nierhoff, T. and Prömel, H.-J. (2001) Lower bounds for approximation algorithms for the Steiner tree problem. In: Proceedings of the 27th International Workshop on Graph-Theoretic Concepts in Computer Science (2001).

Full text not available from this repository.


The Steiner tree problem asks for a shortest subgraph connecting a given set of terminals in a graph. It is known to be APX-complete, which means that no polynomial time approximation scheme can exist for this problem, unless P=NP. Currently, the best approximation algorithm for the Steiner tree problem has a performance ratio of <span class='mathrm'>1.55</span>, whereas the corresponding lower bound is smaller than <span class='mathrm'>1.01</span>. In this paper, we provide for several Steiner tree approximation algorithms lower bounds on their performance ratio that are much larger. For two algorithms that solve the Steiner tree problem on quasi-bipartite instances, we even prove lower bounds that match the upper bounds. Quasi-bipartite instances are of special interest, as currently all known lower bound reductions for the Steiner tree problem in graphs produce such instances.

Item Type:Conference or Workshop Item (UNSPECIFIED)
Uncontrolled Keywords:Steiner trees, Approximation algorithms, Combinatorial optimization, Graph algorithms, Hypergraphs, set systems, and designs
Subjects:Mathematical and Computer Sciences > Computer Science
Divisions:Department of Mathematics and Computer Science > Institute of Computer Science > Algorithmic Bioinformatics Group
ID Code:355
Deposited By: Admin Administrator
Deposited On:14 Apr 2009 14:40
Last Modified:14 Apr 2009 14:40

Repository Staff Only: item control page