Online Generalized Network Design Under (Dis)Economies of Scale

Abstract

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)={\sigma }_e+{\xi }_e\cdot x^{{\alpha }_e}$ if $x>0$ (and zero if $x=0$), where the exponent ${\alpha }_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 $\Theta \left({\max }_{e\in E}{\left(\frac{{\sigma }_e}{{\xi }_e}\right)}^{1/{\alpha }_e}\right)$ when ${\alpha }_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.

20 pages