非表示:
キーワード:
-
要旨:
We study several old and new algorithms for computing lower and upper bounds
for the
Steiner problem in networks using dual-ascent and primal-dual strategies. We
show that
none of the known algorithms can both generate tight lower bounds empirically
and
guarantee their quality theoretically; and we present a new algorithm which
combines
both features. The new algorithm has running time $O(re\log n)$ and guarantees
a ratio
of at most two between the generated upper and lower bounds, whereas the fastest
previous algorithm with comparably tight empirical bounds has running time
$O(e^2)$
without a constant approximation ratio. Furthermore, we show that the
approximation
ratio two between the bounds can even be achieved in time $O(e + n\log n)$,
improving
the previous time bound of $O(n^2\log n)$.
