Online Generalized Network Design Under (Dis)Economies of Scale

• 成果类型: Article
• 署名作者: Nagarajan, Viswanath; Wang, Lily
• 署名单位: University of Michigan System; University of Michigan
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2022.1349
• 发表日期: 2024
• 关键词: approximation algorithms; steiner

摘要

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 resource. The objective is to minimize the total cost P E. The cost incurred by a resource e E E is some function fe of the total load le on that eEE fe(le). We focus on cost functions that exhibit (dis)economies of scale. These functions are of the form fe(x) = sigma e + xi e center dot x alpha e if x > 0 (and zero if x = 0), in which the exponent alpha e >_ 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 Theta(maxeEE(sigma e xi e)1=alpha e) when alpha e is constant for all e 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. We also demonstrate the practical performance of our online algorithm on instances of multicommodity routing.