  A covering integer program (CIP) is a mathematical program of the form: min
{c^T x : Ax >= 1, 0 <= x <= u, x integer}, where A is an m x n matrix, and c
and u are n-dimensional vectors, all having non-negative entries. In the online
setting, the constraints (i.e., the rows of the constraint matrix A) arrive
over time, and the algorithm can only increase the coordinates of vector x to
maintain feasibility. As an intermediate step, we consider solving the covering
linear program (CLP) online, where the integrality requirement on x is dropped.
  Our main results are (a) an O(log k)-competitive online algorithm for solving
the CLP, and (b) an O(log k log L)-competitive randomized online algorithm for
solving the CIP. Here k<=n and L<=m respectively denote the maximum number of
non-zero entries in any row and column of the constraint matrix A. By a result
of Feige and Korman, this is the best possible for polynomial-time online
algorithms, even in the special case of set cover.
