Minimum-Cost Network Design with (Dis)economies of Scale
Minimum-Cost Network Design with (Dis)economies of Scale
复制标题
具有规模经济（不经济）的最低成本网络设计
DOI：
10.1137/110825959
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
Lisa Zhang
中科院分区：
文献类型：
--
作者：
M. Andrews;S. Antonakopoulos;Lisa Zhang
给定一个网络、一组需求和一个成本函数 f(.)，最小成本网络设计问题是路由所有需求，目标是最小化 sum_ef(l_e)，其中 l_e 是路由下的总流量负载。我们重点关注形式为 f(x) = s + x^a 的成本函数，其中 x > 0，且 f(0) = 0。对于具有正启动成本 s > 0 的 1。现在，成本函数 f(.) 既不是次加法，也不是超加法。其动机是在支持一组流量需求时最大限度地减少网络范围的能源消耗。人们普遍认为，对于某些计算和通信设备来说，处理速度加倍会使能耗增加一倍以上。因此，用经济学的术语来说，这样的成本函数反映了规模不经济。我们首先讨论为什么现有的路由技术（例如随机舍入和树度量嵌入）无法直接推广。然后我们提出我们的主要贡献，这是一种多对数近似算法。我们通过首先推导出相关的有容量最小成本流问题的双标准近似来获得此结果，我们认为该问题本身就很有趣。我们解决这个问题的方法建立在 Chekuri-Khanna-Shepherd 的良好链接分解、Khandekar-Rao-Vazirani 的通过匹配构造扩展器以及 Rao-Zhou 的良好连接图中的边不相交路由的基础上。然而，我们还开发了新技术，使我们能够控制总成本，这在上述文献中并不是一个问题。
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 sum_e f(l_e), where l_e is the total traffic load under the routing. We focus on cost functions of the form f(x) = s + x^a for x >, 0, with f(0) = 0. For a 1 with a positive startup cost s >, 0. Now, the cost function f(.) is neither sub additive nor super additive. 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 Khandekar-Rao-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.