Approximating Directed Buy-at-Bulk Network Design

Buy-at-bulk network design is a well-known problem that has been researched extensively on undirected graphs. In this paper, we initiate the theoretical study of the same problem on directed graphs, thus capturing real-life situations where the cost of installing capacity on an edge is asymmetric with respect to direction, as e.g. in the design of wireless and satellite communication networks.

More specifically, we develop two approximation algorithms for directed buy-at-bulk network design in the non-uniform cost model. Combined, they achieve a ratio of

$O \big( \! \min \big\{ k^{1 / 2 + \epsilon}, n^{4 / 5 + \epsilon} \big\} \big)$

for any constant

ε

> 0, where

n

is the number of nodes of the network and

k

is the number of demand pairs to be connected. Further, the above ratio is independent of the amount of traffic flow requested by each demand pair, which may vary arbitrarily, and it can be remarkably improved when all demand pairs share a common sink (or a common source, symmetrically).

To the best of our knowledge, this is the first non-trivial approximation factor established for the aforementioned problem, and naturally it also applies to more restricted cost models, such as the uniform and rent-or-buy models. Moreover, it essentially matches the best currently known approximation guarantees for directed Steiner forest, which may be viewed as a special case of directed buy-at-bulk network design.