We consider a generalization of the classical Steiner tree problem
in graphs. Given a graph G=(V,E), and a subset S of the vertices (called
terminals), find a minimum weight tree that includes all the vertices in S.
We address the case when the edges and the vertices have weights associated
with them (most previous work addresses only the case when edges have
weights). Klein and Ravi gave a simple greedy algorithm that gives an
approximation factor of 2 log k. We show that for the unit weight case
we can obtain an "optimal" approximation factor of log k, and for the
weighted case we obtain a factor of about 1.6 log k. This problem is at least
as hard to approximate as the set cover problem for which there is evidence
to argue that log k is the best approximation factor possible.
(Joint work with Samir Khuller.)