• search hit 38 of 111
Back to Result List

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.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Metadaten
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
Verstanden ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.