论文标题
（DIS）规模经济的在线广义网络设计
Online Generalized Network Design Under (Dis)Economies of Scale
论文作者
论文摘要
我们考虑了一个一般的在线网络设计问题，其中n请求的顺序随着时间的推移而到达，每个请求都需要使用可用资源的某个子集。任何资源E所产生的成本是该资源上总负载$ l_e $的某些功能$ f_e $。目的是最大程度地减少总成本$ \ sum_ {e \ in E} f_e（l_e）$。我们专注于表现出（DIS）规模经济的成本功能，这些功能是$ f_e（x）=σ_e +ξ_e + cdot x^{α_e} $（如果$ x> 0 $）（如果$ x = 0 $），expentent $α_e\α_e\ ge 1 $。这些功能下的优化问题由于在节能计算中的应用而受到了最近的关注。我们的主要结果是具有紧密竞争比$θ\ left的确定性在线算法（\ max_ {e \ in e} \ left（\ frac {σ_e} {σ_e} {ξ_e} \ right）^{1/α_e} \ right）该框架适用于无向图和有向图中的各种网络设计问题，包括多商品路由，Steiner Tree Tree/Forest连接性和设定连接性。实际上，我们的在线竞争比率甚至符合通用网络设计的先前最佳（离线）近似比。
We consider a general online network design problem where a sequence of N requests arrive over time, each of which needs to use some subset of the available resources E. The cost incurred by any resource e is some function $f_e$ of the total load $L_e$ on that resource. The objective is to minimize the total cost $\sum_{e\in E} f_e(L_e)$. We focus on cost functions that exhibit (dis)economies of scale, that are of the form $f_e(x) = σ_e + ξ_e\cdot x^{α_e}$ if $x>0$ (and zero if $x=0$), where the exponent $α_e\ge 1$. Optimization problems under these functions have received significant recent attention due to applications in energy-efficient computing. Our main result is a deterministic online algorithm with tight competitive ratio $Θ\left(\max_{e\in E} \left(\frac{σ_e}{ξ_e}\right)^{1/α_e}\right)$ when $α_e$ is constant for all $e\in E$. This framework is applicable to a variety of network design problems in undirected and directed graphs, including multicommodity routing, Steiner tree/forest connectivity and set-connectivity. In fact, our online competitive ratio even matches the previous-best (offline) approximation ratio for generalized network design.
