ملخص: Let G=(V,E) be an undirected graph with costs on the edges specified by . A Steiner tree is any tree of G which spans all nodes in a given subset R of V. When VR is a stable set of G, then (G,R) is called quasi-bipartite. Rajagopalan and Vazirani [SODA'99, 1999, pp. 742–751] introduced the notion of quasi-bipartiteness and showed that the Iterated 1-Steiner heuristic always produces a Steiner tree of total cost at most the optimal when (G,R) is quasi-bipartite and w is a metric. In this paper, we give a more direct and much simpler proof of this result. Next, we show how a bit scaling approach yields a polynomial time implementation of the Iterated 1-Steiner heuristic. This gives a -approximation algorithm for the problem considered by Rajagopalan and Vazirani. (We refer however to the recent and independent developments by Robins and Zelikovsky [SODA'00, 2000] for better bounds and algorithms.) Finally, our bit scaling arguments are not standard and we are the first to adapt bit scaling techniques to the design of approximation algorithms.

لغة: إنجليزية