Online covering with lq-norm objectives and applications to network design

• 成果类型: Article
• 署名作者: Shen, Xiangkun; Nagarajan, Viswanath
• 署名单位: University of Michigan System; University of Michigan
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-019-01409-9
• 发表日期: 2020
• 页码: 155-182
• 关键词: primal-dual algorithms

摘要

We consider fractional online covering problems withlq-norm objectives as well as its dual packing problems. The problem of interest is of the formmin{f(x):Ax >= 1,x >= 0}wheref(x)= n-ary sumation ece||x(Se)||qeis the weighted sum oflq-norms andAis a non-negative matrix. The rows ofA(i.e. covering constraints) arrive online over time. We provide an onlineO(logd+log rho)-competitive algorithm where rho=amaxaminanddis the maximum of the row sparsity ofAandmax|Se|This is based on the online primal-dual framework where we use the dual of the above convex program. Our result is nearly tight (even in the linear special case), and it expands the class of convex programs that admit online algorithms. We also provide two applications where such convex programs arise as relaxations of discrete optimization problems, for which our result leads to good online algorithms. In particular, we obtain an improved online algorithm (by two logarithmic factors) for non-uniform buy-at-bulk network design and a poly-logarithmic competitive ratio for throughput maximization underlp-norm capacities.