Online Generalized Network Design Under (Dis)Economies of Scale

We consider a general online network design problem in which 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 a resource $e\in E$ is some function f_e of the total load ${\mathcal{\ell }}_e$ on that resource. The objective is to minimize the total cost ${\sum }_{e\in E}{f}_e({\mathcal{\ell }}_e)$. We focus on cost functions that exhibit (dis)economies of scale. These functions are of the form $f_e(x)={\sigma }_e+{\xi }_e·x^{{\alpha }_e}$ if x > 0 (and zero if x = 0), in which the exponent ${\alpha }_e\ge 1$. Optimization problems under these functions have received significant recent attention because of applications in energy-efficient computing. Our main result is a deterministic online algorithm with tight competitive ratio $\mathrm{\Theta }({\text{max}}_{e\in E}{(\frac{{\sigma }_e}{{\xi }_e})}^{1/{\alpha }_e})$ 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. We also demonstrate the practical performance of our online algorithm on instances of multicommodity routing.

Funding: This work was supported by the Directorate for Computer and Information Science and Engineering [Grant CCF-1750127] and the Division of Civil, Mechanical and Manufacturing Innovation [Grant CMMI-1940766].