Minimum-Cost Network Design with (Dis)economies of Scale

Given a network, a set of demands and a cost function f (·), the min-cost network design problem is to route all demands with the objective of minimizing e f ( e ), where e is the total traffic load under the routing. We focus on cost functions of the form f (x) = + x for x > 0, with f (0) = 0. For 1, f (·) is subadditive and exhibits behavior consistent with economies of scale. This problem 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 startup cost > 0. Now, the cost function f (·) is neither subadditive nor superadditive. This is motivated by minimizing network-wide energy consumption when supporting a set of traffic demands. It is commonly accepted that, for some computing and communication devices, doubling processing speed more than doubles the energy consumption. Hence, in Economics parlance, such a cost function reflects diseconomies of scale. 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-Shepherd [12], the construction of expanders via matchings due to KhandekarRao-Vazirani [22], and edge-disjoint routing in well-connected graphs due to Rao-Zhou [29].