2020/07/15 by Viswanath Nagarajan, Lily Wang, Nagarajan, Viswanath +1
Computer Science · Engineering · #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Optimization and Search Problems #Smart Parking Systems Research
paper · pdf · doi:10.48550/arxiv.2007.07721
openalex publication_date 2020/07/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 fe of the total load Le on that resource. The objective is to minimize the total cost ∑e∈ E fe(Le). We focus on cost functions that exhibit (dis)economies of scale, that are of the form fe(x) = σe + ξe⋅ xαe if x>0 (and zero if x=0), where the exponent αe≥ 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 Θ(maxe∈ E ((σe)/(ξe))1/αe) when αe is constant for all e∈ 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.