Abstract
We present online algorithms for covering and packing problems with (non-linear) convex objectives. The convex covering problem is to minimize a monotone convex function subject to covering constraints. In the online version, a new covering constraint is revealed in each step and the algorithm is required to maintain a feasible and monotonically non-decreasing assignment over time. This framework captures several natural problems that have been individually studied previously. We present an online algorithm for the problem, and show that its competitive ratio is nearly the best possible. This allows us to obtain algorithms for several application problems whose performance either improves on, or nearly matches, their respective best known previous results. We also consider a convex packing problem which is the Fenchel dual of the convex covering program. We use a primal-dual approach that naturally gives algorithms for this dual problem as well. As an application, this gives us online algorithms for maximizing social welfare with (non-linear convex) production costs.