Approximating Sparse Covering Integer Programs Online

• 成果类型: Article
• 署名作者: Gupta, Anupam; Nagarajan, Viswanath
• 署名单位: Carnegie Mellon University; International Business Machines (IBM); IBM USA
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2014.0652
• 发表日期: 2014
• 页码: 998-1011
• 关键词: algorithms; packing

摘要

A covering integer program (CIP) is a mathematical program of the form min {c(T)x vertical bar Ax >= 1, 0 <= x <= u, x is an element of Z(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(logk)-competitive online algorithm for solving the CLP, and (b) an O(logk.logl)-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.