BIRS Workshop Lecture Videos
Online Covering with Sum of Lq-norm Objectives Nagarajan, Viswanath
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 Citations and Data
Attribution-NonCommercial-NoDerivatives 4.0 International