BIRS Workshop Lecture Videos

Banff International Research Station Logo

BIRS Workshop Lecture Videos

Online Covering with Sum of Lq-norm Objectives Nagarajan, Viswanath

Description

We consider fractional covering problems with Lq-norm objectives, where the covering requirements arrive online. This can be viewed as a convex programming problem, and we provide a log-competitive algorithm based on a primal-dual approach. This result expands the class of convex programs with good online algorithms. As applications, we obtain online algorithms for non-uniform buy-at-bulk network design and throughput maximization under Lq-norm capacities.

Item Media

Item Citations and Data

Rights

Attribution-NonCommercial-NoDerivatives 4.0 International