Online Covering with Sum of ell_q-Norm Objectives.

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

Abstract: We consider fractional online covering problems with

e l l_{q}

-norm objectives. The problem of interest is of the form

m i n f (x), :, A x g e 1, x g e 0

where

f (x) = s u m_{e} c_{e} | x (S_{e}) |_{q_{e}}

is the weighted sum of

e l 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 (l o g d + l o g h o)

-competitive algorithm where

h o = f r a c m a x a_{i j} m i n a_{i j}

and

d

is the maximum of the row sparsity of

A

and

m a x | 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

e l l_{p}

-norm edge capacities.

Recommendations

Cited in

(2)

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)