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...

  • Capacity-efficient strategy for 100% dual-failure restorability in optical mesh networks utilising reconfigurable p-cycles and a forcer filling concept. Sue, C.-C.; Du, J.-Y. // IET Communications;Feb2009, Vol. 3 Issue 2, p198 

    The problem of achieving 100% dual-failure restorability utilising reconfigurable p-cycle mechanisms has been investigated via three different p-cycle mechanisms derived from the integer linear programming model; complete-repair (CRP), incremental-repair (IRP) and dynamic-repair (DRP). An...

  • 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...

  • Analysis of integer programming algorithms with L-partition and unimodular transformations. Kolokolov, A.; Orlovskaya, T.; Rybalka, M. // Automation & Remote Control;Feb2012, Vol. 73 Issue 2, p369 

    We study algorithms for solving integer linear programming problems, in particular, set packing and knapsack problems. We pay special attention to algorithms of lexicographic enumeration of L-classes and their combinations with other approaches. We study the problems of using unimodular...


Read the Article


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

Try another library?
Sign out of this library

Other Topics