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

📧 Request an update