Online Packing and Covering Framework with Convex Objectives

Original · EN

We consider online fractional covering problems with a convex objective, where the covering constraints arrive over time. Formally, we want to solve {f(x) Ax≥ 1, x≥ 0}, where the objective function f:Rⁿ→ R is convex, and the constraint matrix Aₘ× ₙ 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 {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 ℓₚ-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.