On the approximability of the Steiner tree problem
Please always quote using this URN:urn:nbn:de:0296-matheon-2841
- We show that it is not possible to approximate the minimum Steiner tree problem within 1+1/162 unless RP=NP. The currently best known lower bound is 1+ 1/400. The reduction is from Hastad’s nonapproximability result for maximum satisfiability of linear equation modulo 2. The improvement on the nonapproximability ratio is mainly based on the fact that our reduction does not use variable gadgets. This idea was introduced by Papadimitriou and Vempala.
Author: | Martin Thimm |
---|---|
URN: | urn:nbn:de:0296-matheon-2841 |
Referee: | Hans Jürgen Prömel |
Document Type: | Preprint, Research Center Matheon |
Language: | English |
Date of first Publication: | 2005/12/11 |
Release Date: | 2005/07/11 |
Preprint Number: | 285 |