Approximating sparse covering integer programs online

Anupam Gupta, Viswanath Nagarajan

Research output: Contribution to journalArticlepeer-review


A covering integer program (CIP) is a mathematical program of the form min{cx | Ax ≥ 1,0 ≤ x ≤ u, x ∈ ℤn}, where all entries in A, c , u are nonnegative. 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 x to maintain feasibility. As an intermediate step, we consider solving the covering linear program (CLP) online, where the integrality constraints are dropped. Our main results are (a) an O(log k)-competitive online algorithm for solving the CLP, and (b) an O(log k·logℓ)-competitive randomized online algorithm for solving the CIP. Here k ≤ n and ℓ ≤ m respectively denote the maximum number of nonzero entries in any row and column of the constraint matrix A. Our algorithm is based on the online primal-dual paradigm, where a novel ingredient is to allow dual variables to increase and decrease throughout the course of the algorithm. It is known that this result is the best possible for polynomial-time online algorithms, even in the special case of set cover (where all entries in A, c , and u are 0 or 1.

Original languageEnglish (US)
Pages (from-to)998-1011
Number of pages14
JournalMathematics of Operations Research
Issue number4
StatePublished - Nov 1 2014


  • Covering integer programs
  • Linear programming
  • Online algorithms

ASJC Scopus subject areas

  • General Mathematics
  • Computer Science Applications
  • Management Science and Operations Research


Dive into the research topics of 'Approximating sparse covering integer programs online'. Together they form a unique fingerprint.

Cite this