# Online Packing and Covering Framework with Convex Objectives

arXiv: https://arxiv.org/abs/1412.8347 · HTML: https://mlsanity.com/paper/1412.8347/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 Dec 2014.

## Built on by (most cited first, 1 of 1)

- [Learning-Augmented Algorithms for Online Concave Packing and Convex Covering Problems](https://mlsanity.com/paper/2411.08332/) (2024)

## Abstract (arXiv)

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.