Online Covering with Sum of ell_q-Norm Objectives.

DOI10.4230/LIPICS.ICALP.2017.12zbMATH Open1441.68297arXiv1705.02194OpenAlexW2964206148MaRDI QIDQ5111341FDOQ5111341

Viswanath Nagarajan, Xiangkun Shen

Publication date: 27 May 2020

Abstract: We consider fractional online covering problems with $el{l}_q$-norm objectives. The problem of interest is of the form $minf(x),:,Axge1,xge0$ where $f(x)=su{m}_e{c}_e|x(S_e){|}_{q_e}$ is the weighted sum of $el{l}_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(logd+logho)$-competitive algorithm where $ho=fracmax{a}_{ij}min{a}_{ij}$ 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 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 $el{l}_p$-norm edge capacities.

Full work available at URL: https://arxiv.org/abs/1705.02194

zbMATH Keywords

online algorithmthroughput maximizationbuy-at-bulk network designconvex objectivescovering/packing problem

Mathematics Subject Classification ID

Convex programming (90C25) Online algorithms; streaming algorithms (68W27) Programming involving graphs or networks (90C35) Combinatorial optimization (90C27)

Cited In (2)

• Title not available (Why is that?)
• Online covering with \(\ell_q\)-norm objectives and applications to network design

   Recommendations

• Online covering with \(\ell_q\)-norm objectives and applications to network design 👍 👎
• Online Primal-Dual Algorithms for Covering and Packing 👍 👎
• Algorithms – ESA 2005 👍 👎
• Approximating Sparse Covering Integer Programs Online 👍 👎
• Approximating Sparse Covering Integer Programs Online 👍 👎

This page was built for publication: Online Covering with Sum of $ell_q$-Norm Objectives.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5111341)