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) mid Ax≥ 1,, x≥ 0, where the objective function f:ℝnrightarrow ℝ 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^intercal y - g(μ) mid A^intercal y ≤ μ,, y≥ 0, where g is a convex function. In the online setting, variables y and columns of A^intercal 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.