2009/04/06 by David Pritchard, Pritchard, David, Deeparnab Chakrabarty +1
Computer Science · Engineering · #Advanced Graph Theory Research #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Optimization and Packing Problems #Vehicle Routing Optimization Methods
paper · pdf · doi:10.48550/arxiv.0904.0859
openalex publication_date 2009/04/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The main focus of this paper is a pair of new approximation algorithms for certain integer programs. First, for covering integer programs min cx: Ax >= b, 0 <= x <= d where A has at most k nonzeroes per row, we give a k-approximation algorithm. (We assume A, b, c, d are nonnegative.) For any k >= 2 and eps>0, if P != NP this ratio cannot be improved to k-1-eps, and under the unique games conjecture this ratio cannot be improved to k-eps. One key idea is to replace individual constraints by others that have better rounding properties but the same nonnegative integral solutions; another critical ingredient is knapsack-cover inequalities. Second, for packing integer programs max cx: Ax <= b, 0 <= x <= d where A has at most k nonzeroes per column, we give a (2k2+2)-approximation algorithm. Our approach builds on the iterated LP relaxation framework. In addition, we obtain improved approximations for the second problem when k=2, and for both problems when every Aij is small compared to bi. Finally, we demonstrate a 17/16-inapproximability for covering integer programs with at most two nonzeroes per column.