Online Covering with Sum of ${\mathrm{\ell }}_q$-Norm Objectives

We consider fractional online covering problems with ${\mathrm{\ell }}_q$-norm objectives. The problem of interest is of the form $\min{ f(x) ,:, Ax\ge 1, x\ge 0}$where$f(x)=\sum_{e} c_e |x(S_e)|{q_e} $istheweightedsumof$\ell_q$-normsand$A$isanon-negativematrix\mathrm{.}Therowsof$A$ (i.e. covering constraints) arrive online over time. We provide an online $O(\log d+\log \rho)$-competitivealgorithmwhere$\rho = \frac{\max a{ij}}{\min a_{ij}}$and$d$isthemaximumoftherowsparsityof$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 expands the class of convex objectives that admit good online algorithms: prior results required a monotonicity condition on the objective $f$ which is not satisfied here. This result is nearly tight even for the linear special case. As direct applications we obtain (i) improved online algorithms for non-uniform buy-at-bulk network design and (ii) the first online algorithm for throughput maximization under ${\mathrm{\ell }}_p$-norm edge capacities.