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.Abstract
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 |
URI: | http://sro.sussex.ac.uk/id/eprint/24660 |