Please help transcribe this video using our simple transcription tool. You need to be logged in to do so.


Given a network, a set of demands and a cost function $f(cdot)$, the min-cost n etwork design problem is to route all demands with the objective of minimizing $ sum_e f(ell_e)$, where $ell_e$ is the total traffic load under the routing. We focus on cost functions of the form $f(x)= sigma + x^{alpha}$ for $x > 0$, with $f(0) = 0$. For $alpha le 1$, $f(cdot)$ is subadditive and exhibits beha vior consistent with economies of scale. This problem corresponds to the well-s tudied Buy-at-Bulk network design problem and admits polylogarithmic approximati on and hardness.

In this paper, we focus on the less studied scenario of $alpha > 1$ with a posi tive startup cost $sigma > 0$. Now, the cost function $f(cdot)$ is neither sub additive 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 mo re than doubles the energy consumption. Hence, in Economics parlance, such a cos t function reflects emph{diseconomies of scale}.

We begin by discussing why existing routing techniques such as randomized roundi ng and tree-metric embedding fail to generalize directly. We then present our m ain contribution, which is a polylogarithmic approximation algorithm. We obtain this result by first deriving a bicriteria approximation for a related capacitat ed min-cost flow problem that we believe is interesting in its own right. Our ap proach for this problem builds upon the well-linked decomposition due to Chekuri -Khanna-Shepherd~cite{ChekuriKS05}, the construction of expanders via matchings due to Khandekar-Rao-Vazirani~cite{KhandekarRV06}, and edge-disjoint routing i n well-connected graphs due to Rao-Zhou~cite{RaoZ06}. 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.

Questions and Answers

You need to be logged in to be able to post here.