Approximating shallow-light trees
Guy Kortsarz, David Peleg · Symposium on Discrete Algorithms · 1997
This paper deals with the problem of constructing Steiner trees of minimum weight with diameter bounded by d, spanning a given set V of {nu} vertices in a graph. Exact solutions or logarithmic ratio approximation algorithms were known before for the cases of d {le} 5. Here we give a polynomial time approximation algorithm of ratio d log {nu} for constant d, and an algorithm of ratio {nu}{sup {epsilon}}, for any fixed 0 < {epsilon} < 1, for general d.