Online Generalized Network Design Under (Dis)Economies of Scale

We consider a general online network design problem where a sequence of N requests arrive over time, each of which needs to use a subset of the available resources E. The cost incurred by a resource e ∊ E is some function fe of its total load ℓe. The objective is to minimize the total cost Σe∊E fe(ℓe). We focus on cost functions that exhibit (dis)economies of scale, which are of the form if x > 0 (and zero if x = 0), where the exponent αe ≥ 1. Our main result is a deterministic online algorithm with tight competitive ratio when αe is constant. This framework is applicable to many network design problems, including multicommodity routing, Steiner tree/forest connectivity and set-connectivity Even in special cases such as multicommodity routing in undirected graphs with edge-costs, this is the first online algorithm to handle non-uniform resource cost and with a competitive ratio independent of the network size and number of requests. Our online competitive ratio also matches the previous-best offline approximation ratio. Our approach is based on the online primal-dual method for convex programs.