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, the construction of expanders via matchings due to KhandekarRao-Vazirani, and edge-disjoint routing in well-connected graphs due to Rao-Zhou. 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.