A New Approximation Algorithm for the Selective Single-Sink Buy-at-Bulk Problem in Network Design

摘要

The Selective Single-Sink Buy-at-Bulk problem was proposed by Awerbuch and Azar (FOCS 1997). For a long time, the only known non-trivial approach to approximate this problem is the tree-embedding method initiated by Bartal (FOCS 1996). In this paper, we give a thoroughly different approximation approach for the problem with approximation ratio O(1/2/q), where q is the number of source terminals in the problem instance. Our approach is based on a mixed strategy of LP-rounding and the greedy method. When the number q (which is always at most n) is relatively small (say, q = o(log~2 n)), our approximation ratio O(1/2/q) is better than the currently known best ratio O(log n), where n is the number of vertices in the input graph.