MINIMUM-COST NETWORK DESIGN WITH (DIS)ECONOMIES OF SCALE.

Given a network, a set of demands, and a cost function ƒ(·), the min-cost network design problem is to route all demands with the objective of minimizing Σe ƒ(le), where le is the total traffic load under the routing. We focus on cost functions of the form ƒ(x) = σ + xα for x > 0, with ƒ (0) = 0. For α ≤1, ƒ(·) is subadditive. This case corresponds to the well-studied buy-at-bulk network design problem and admits polylogarithmic approximation and hardness. In this paper, we focus on the less-studied scenario of α > 1 with a positive start-up cost σ > 0. Now, the cost function ƒ(·) is neither subadditive nor superadditive. It aims to model a range of computing and communication devices for which doubling processing speed more than doubles their power consumption. We begin by discussing why existing routing techniques such as randomized rounding and tree-metric embedding fail to generalize directly. We then present our main contribution, which is a polylogarithmic approximation algorithm. We obtain this result by first deriving a bicriteria approximation for a related capacitated min-cost flow problem that we believe is interesting in its own right. Our approach for this problem builds upon the well-linked decomposition due to Chekuri, Khanna, and Shepherd [Proceedings of ACM STOC, ACM, New York, pp. 183-192], the construction of expanders via matchings due to Khandekar, Rao, and Vazirani [J. ACM, 56 (2009), 19], and edge-disjoint routing in well-connected graphs due to Rao and Zhou [SIAM J. Comput., 39 (2010), pp. 1856-1887]. However, we also develop new techniques that allow us to keep a handle on the total cost, which was not a concern in the aforementioned literature. [ABSTRACT FROM AUTHOR]