Online covering with ℓq-norm objectives and applications to network design

• Published in: Mathematical programming 2020, Vol.184 (1-2), p.155-182
• Main Authors: Shen, Xiangkun, Nagarajan, Viswanath
• Format: Article
• Language: English
• Subjects: Algorithms; Applications programs; Calculus of Variations and Optimal Control; Optimization; Combinatorics; Full Length Paper; Mathematical and Computational Physics; Mathematical Methods in Physics; Mathematics; Mathematics and Statistics; Mathematics of Computing; Network design; Norms; Numerical Analysis; Optimization; Theoretical
• ISSN: 0025-5610; 1436-4646
• DOI: 10.1007/s10107-019-01409-9

We consider fractional online covering problems with ℓ q -norm objectives as well as its dual packing problems. The problem of interest is of the form min { f ( x ) : A x ≥ 1 , x ≥ 0 } where f ( x ) = ∑ e c e ‖ x ( S e ) ‖ q e is the weighted sum of ℓ q -norms and A is a non-negative matrix. The rows of A (i.e. covering constraints) arrive online over time. We provide an online O ( log d + log ρ ) -competitive algorithm where ρ = a max a min and d is the maximum of the row sparsity of A and max | S e | . 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 under ℓ p -norm capacities.