Information Processing Letters · 2003 · 67 citations · 6 references
ComputingComputer ScienceMathematicsAlgorithmsOptimizationApproximation AlgorithmsCombinatorial OptimizationGraph AlgorithmsGraph TheoryRandomized Approximation AlgorithmsSteiner Tree ApproximationSteiner Tree ProblemTree Algorithms
The terminal Steiner tree problem is a special version of the Steiner tree problem, where a Steiner minimum tree has to be found in which all terminals are leaves. We prove that no polynomial time approximation algorithm for the terminal Steiner tree problem can achieve an approximation ratio less than (1−o(1))ln n unless NP has slightly superpolynomial time algorithms. Moreover, we present a polynomial time approximation algorithm for the metric version of this problem with a performance ratio of 2 ρ , where ρ denotes the best known approximation ratio for the Steiner tree problem. This improves the previously best known approximation ratio for the metric terminal Steiner tree problem of ρ +2.
6
A threshold of ln <i>n</i> for approximating set cover
Uriel Feige · Journal of the ACM · 1998 · 3.1K citations · Full text
Proof verification and hardness of approximation problems
Sanjeev Arora, Carsten Lund, R. Motwani et al. · 1992 · 744 citations
Improved Steiner tree approximation in graphs
Gabriel Robins, Alex Zelikovsky · 2000 · 530 citations
The Steiner problem with edge lengths 1 and 2
Marshall Bern, Paul E. Plassmann · Information Processing Letters · 1989 · 378 citations