Approximating Steiner trees in graphs with restricted weights

Magnús M. Halldórsson
Science Institute, University of Iceland, IS-107 Reykjavik, Iceland.

Shuichi Ueno, Hiroshi Nakao, Yoji Kajitani.
Department of Electrical Engineering, Tokyo Institute of Technology, 3-24 O-Okayama, Meguro-ku, 152 Japan.

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$.