Online Packing and Covering Framework with Convex Objectives

We consider online fractional covering problems with a convex objective, where the covering constraints arrive over time. Formally, we want to solve min{f(x)∣Ax≥1,x≥0}, where the objective function f:Rn→R is convex, and the constraint matrix Am×n is non-negative. The rows of A arrive online over time, and we wish to maintain a feasible solution x at all times while only increasing coordinates of x. We also consider "dual" packing problems of the form max{c⊺y−g(μ)∣A⊺y≤μ,y≥0}, where g is a convex function. In the online setting, variables y and columns of A⊺ arrive over time, and we wish to maintain a non-decreasing solution (y,μ).
We provide an online primal-dual framework for both classes of problems with competitive ratio depending on certain "monotonicity" and "smoothness" parameters of f; our results match or improve on guarantees for some special classes of functions f considered previously.
Using this fractional solver with problem-dependent randomized rounding procedures, we obtain competitive algorithms for the following problems: online covering LPs minimizing ℓp-norms of arbitrary packing constraints, set cover with multiple cost functions, capacity constrained facility location, capacitated multicast problem, set cover with set requests, and profit maximization with non-separable production costs. Some of these results are new and others provide a unified view of previous results, with matching or slightly worse competitive ratios.