File(s) not publicly available
Approximation hardness of the Steiner tree problem on graphs
presentation
posted on 2023-06-08, 05:24 authored by Miroslav ChlebikMiroslav Chlebik, Janka Chlebíková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.
History
Publication status
- Published
ISSN
0302-9743Publisher
Springer Berlin / HeidelbergExternal DOI
Volume
2368Pages
10.0Presentation Type
- paper
Event name
8th Scandinavian Workshop on Algorithm TheoryEvent location
TURKU, FINLANDEvent type
conferenceISBN
3-540-43866-1Department affiliated with
- Mathematics Publications
Notes
Lecture Notes in Computer Science. Algorithm Theory, SWAT 2002Full text available
- No
Peer reviewed?
- Yes
Editors
M Penttonen, EM SchmidtLegacy Posted Date
2012-02-06Usage metrics
Categories
No categories selectedKeywords
Licence
Exports
RefWorks
BibTeX
Ref. manager
Endnote
DataCite
NLM
DC