TITLE

Approximating Sparse Covering Integer Programs Online

AUTHOR(S)
Gupta, Anupam; Nagarajan, Viswanath
PUB. DATE
November 2014
SOURCE
Mathematics of Operations Research;Nov2014, Vol. 39 Issue 4, p998
SOURCE TYPE
Academic Journal
DOC. TYPE
Article
ABSTRACT
A covering integer program (CIP) is a mathematical program of the form min{cT x | Ax ≥ 1, 0 ≤ x ≤ u, x ∈ Zn}, 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 l)-competitive randomized online algorithm for solving the CIP. Here k ≤ n and l ≤ 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.
ACCESSION #
111113314

 

Share

Read the Article

Courtesy of THE LIBRARY OF VIRGINIA

Sorry, but this item is not currently available from your library.

Try another library?
Sign out of this library

Other Topics