Approximating Steiner trees in graphs with restricted weights
Magn�s M. Halld�rsson, Shuichi Ueno, Hiroshi Nakao, Yoji Kajitani · Networks · 1998
We analyze the approximation ratio of the average distance heuristic for the Steiner tree problem on graphs and prove nearly tight bounds for the cases of complete graphs with binary weights {1, d} or weights in the interval [1, d], where d ≤ 2. The improvement over other analyzed algorithms is a factor of about e ≈ 2.718. © 1998 John Wiley & Sons, Inc. Networks 31: 283–292, 1998