Approximating Sparse Covering Integer Programs Online

Gupta, Anupam; Nagarajan, Viswanath
November 2014
Mathematics of Operations Research;Nov2014, Vol. 39 Issue 4, p998
Academic Journal
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.


Related Articles

  • GENERALIZED RESOLUTION AND CUTTING PLANES. Hooker, J. N. // Annals of Operations Research;1988, Vol. 12 Issue 1-4, p217 

    This paper illustrates how the application of integer programming to logic can reveal parallels between logic and mathematics and lead to new algorithms for inference in knowledge-based systems. If logical clauses (stating that at least one of a set of literals is true) are written as...

  • Implicit solution function of P and Z matrix linear complementarity constraints. Xiaojun Chen; Shuhuang Xiang // Mathematical Programming;May2011, Vol. 128 Issue 1/2, p1 

    Using the least element solution of the P and Z matrix linear complementarity problem (LCP), we define an implicit solution function for linear complementarity constraints (LCC). We show that the sequence of solution functions defined by the unique solution of the regularized LCP is...

  • GOMORY CUT.  // Encyclopedia of Operations Research & Management Science;2001, p338 

    A definition of the term "Gomory cut" is presented. It refers to a linear constraint that is added to a linear-programming problem to reduce the solution space without decreasing any integer-valued points. The way that an optimal integer solution corresponds to an extreme point of the reduced...

  • ALTERNATIVE FORMULATIONS OF MIXED INTEGER PROGRAMS. Jeroslow, Robert G. // Annals of Operations Research;1988, Vol. 12 Issue 1-4, p241 

    We study the formation of mixed-integer programming (MIP) constraints through the development of constructions which syntactically parallel the set operations of union, intersection, Cartesian product, and linear affine transformation. In this manner, we are able to both modularize the work of...

  • A Time Bucket Formulation for the Traveling Salesman Problem with Time Windows. Dash, Sanjeeb; Günlük, Oktay; Lodi, Andrea; Tramontani, Andrea // INFORMS Journal on Computing;Winter2012, Vol. 24 Issue 1, p132 

    The traveling salesman problem with time windows (TSPTW) is the problem of finding a minimum-cost path visiting a set of cities exactly once, where each city must be visited within a given time window. We present an extended formulation for the problem based on partitioning the time windows into...

  • FINDING TIME QUANTUM OF ROUND ROBIN CPU SCHEDULING ALGORITHM IN GENERAL COMPUTING SYSTEMS USING INTEGER PROGRAMMING. Mostafa, Samih M.; Rida, S. Z.; Hamad, Safwat H. // International Journal of Research & Reviews in Applied Sciences;2010, Vol. 5 Issue 1, p64 

    In Round Robin Scheduling, the time quantum is fixed and then processes are scheduled such that no process get CPU time more than one time quantum in one go. If time quantum is too large, the response time of the processes is too much which may not be tolerated in interactive environment. If...

  • Cyclic Scheduling via Integer Programs with Circular Ones. Bartholdi III, John J.; Orlin, James B.; Ratliff, H. Donald // Operations Research;Sep/Oct80, Vol. 28 Issue 5, p1074 

    A fundamental problem of cyclic staffing is to size and schedule a minimum-cost workforce so that sufficient workers are on duty during each time period This may be modeled as an integer linear program with a cyclically structured 0-1 constraint matrix We identify a large class of such problems...

  • The Group-Theoretic Structure in the Fixed-Charge Transportation Problem. Kennington, J. L.; Unger, V. E. // Operations Research;Sep/Oct73, Vol. 21 Issue 5, p1142 

    The multiparametric integer programming problem for the right-hand side is to minimize c′t subject to At=b(y), t≧0, t=0 (mod 1), where b(y) can be expressed in the form b(y) = b+F(y), where F is a matrix of constant coefficients, and y is an integer vector parameter. The group...

  • BRANCH-AND-BOUND METHODS: A SURVEY. Lawler, E. L.; Wood, D. E. // Operations Research;Jul/Aug66, Vol. 14 Issue 4, p699 

    The essential features of the branch-and-bound approach to constrained optimization are described, and several specific applications are reviewed. These include integer linear programming (LAND-DOIG and BALAS methods), nonlinear programming (minimization of nonconvex objective functions), the...


Other Topics