Approximation hardness of the Steiner tree problem on graphs

Chlebík, Miroslav and Chlebíková, Janka (2002) Approximation hardness of the Steiner tree problem on graphs. In: 8th Scandinavian Workshop on Algorithm Theory, TURKU, FINLAND.

Full text not available from this repository.


Steiner tree problem in weighted graphs seeks a minimum weight subtree containing a given subset of the vertices (terminals). We show that it is NP-hard to approximate the Steiner tree problem within 96/95. Our inapproximability results are stated in parametric way and can be further improved just providing gadgets and/or expanders with better parameters. The reduction is from Hastad's inapproximability result for maximum satisfiability of linear equations modulo 2 with three unknowns per equation. This was first used for the Steiner tree problem by Thimm whose approach was the main starting point for our results.

Item Type: Conference or Workshop Item (Paper)
Additional Information: Lecture Notes in Computer Science. Algorithm Theory, SWAT 2002
Schools and Departments: School of Mathematical and Physical Sciences > Mathematics
Depositing User: Miroslav Chlebik
Date Deposited: 06 Feb 2012 20:12
Last Modified: 04 Apr 2012 12:38
📧 Request an update