A new approximation algorithm for the Selective Single-Sink Buy-at-Bulk problem in network design |
| |
Authors: | Peng Zhang |
| |
Institution: | 1. School of Computer Science and Technology, Shandong University, Jinan, 250101, China
|
| |
Abstract: | 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(\sqrt{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(log2 n)), our approximation ratio $O(\sqrt{q})$ is better than the currently known best ratio O(logn), where n is the number of vertices in the input graph. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|