Abstract
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 ε>0, if P≠NP this ratio cannot be improved to k−1−ε, and under the unique games conjecture this ratio cannot be improved to k−ε. 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 (2k 2+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 A ij is small compared to b i . Finally, we demonstrate a 17/16-inapproximability for covering integer programs with at most two nonzeroes per column.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Bansal, N., Korula, N., Nagarajan, V., Srinivasan, A.: On k-column sparse packing programs. In: Proc. 14th IPCO, pp. 369–382 (2010). Preliminary version at arXiv:0908.2256
Bar-Yehuda, R., Even, S.: A linear time approximation algorithm for the weighted vertex cover problem. J. Algorithms 2, 198–203 (1981)
Bar-Yehuda, R., Rawitz, D.: Efficient algorithms for integer programs with two variables per constraint. Algorithmica 29(4), 595–609 (2001)
Berman, P.: A d/2 approximation for maximum weight independent set in d-claw free graphs. Nord. J. Comput. 7(3), 178–184 (2000). Preliminary version in Proc. 7th SWAT, pp. 214–219 (2000)
Carr, R.D., Fleischer, L., Leung, V.J., Phillips, C.A.: Strengthening integrality gaps for capacitated network design and covering problems. In: Proc. 11th SODA, pp. 106–115 (2000)
Chakrabarty, D., Goel, G.: On the approximability of budgeted allocations and improved lower bounds for submodular welfare maximization and GAP. In: Proc. 49th FOCS, pp. 687–696 (2008)
Chekuri, C., Mydlarz, M., Shepherd, F.B.: Multicommodity demand flow in a tree and packing integer programs. ACM Trans. Algorithms 3(3), 27 (2007). Preliminary version in Proc. 30th ICALP, pp. 410–425 (2003)
Chekuri, C., Ene, A., Korula, N.: Unsplittable flow in paths and trees and column-restricted packing integer programs. In: Proc. 12th APPROX, pp. 42–55 (2009)
Dinur, I., Guruswami, V., Khot, S., Regev, O.: A new multilayered PCP and the hardness of hypergraph vertex cover. SIAM J. Comput. 34(5), 1129–1146 (2005). Preliminary version in Proc. 35th STOC, pp. 595–601 (2003)
Fujito, T., Yabuta, T.: Submodular integer cover and its application to production planning. In: Proc. 2nd WAOA, pp. 154–166 (2004)
Garg, N., Vazirani, V.V., Yannakakis, M.: Primal-dual approximation algorithms for integral flow and multicut in trees. Algorithmica 18(1), 3–20 (1997). Preliminary version in Proc. 20th ICALP, pp. 64–75 (1993)
Goel, G., Karande, C., Tripathi, P., Wang, L.: Approximability of combinatorial problems with multi-agent submodular cost functions. In: Proc. 50th FOCS, pp. 755–764 (2009)
Grötschel, M., Lovász, L., Schrijver, A.: Geometric Algorithms and Combinatorial Optimization. Springer, Berlin (1988)
Hall, N.G., Hochbaum, D.S.: A fast approximation algorithm for the multicovering problem. Discrete Appl. Math. 15(1), 35–40 (1986)
Håstad, J.: Some optimal inapproximability results. J. ACM 48(4), 798–859 (2001)
Hazan, E., Safra, S., Schwartz, O.: On the complexity of approximating k-set packing. Comput. Complex. 15(1), 20–39 (2006). Preliminary versions in Proc. 6th APPROX, pp. 83–97 (2003)
Hochbaum, D.S.: Approximation algorithms for set covering and vertex cover problems. SIAM J. Comput. 11, 555–556 (1982)
Hochbaum, D.S.: Monotonizing linear programs with up to two nonzeroes per column. Oper. Res. Lett. 32(1), 49–58 (2004)
Hochbaum, D.S., Megiddo, N., Naor, J.S., Tamir, A.: Tight bounds and 2-approximation algorithms for integer programs with two variables per inequality. Math. Program. 62(1), 69–83 (1993)
Hurkens, C.A.J., Schrijver, A.: On the size of systems of sets every t of which have an SDR, with an application to the worst-case ratio of heuristics for packing problems. SIAM J. Discrete Math. 2(1), 68–72 (1989)
Iwata, S., Nagano, K.: Submodular function minimization under covering constraints. In: Proc. 50th FOCS, pp. 671–680 (2009)
Kellerer, H., Pferschy, U., Pisinger, D.: Knapsack Problems. Springer, Berlin (2004)
Khot, S., Ponnuswami, A.K.: Better inapproximability results for MaxClique, Chromatic Number and Min-3Lin-Deletion. In: Proc. 33rd ICALP, pp. 226–237 (2006)
Khot, S., Regev, O.: Vertex cover might be hard to approximate to within 2−ε. J. Comput. Syst. Sci. 74(3), 335–349 (2008). Preliminary version in Proc. 18th CCC, pp. 379–386 (2003)
Kolliopoulos, S.G., Stein, C.: Improved approximation algorithms for unsplittable flow problems. In: Proc. 38th FOCS, pp. 426–436 (1997)
Kolliopoulos, S.G., Young, N.E.: Approximation algorithms for covering/packing integer programs. J. Comput. Syst. Sci. 71(4), 495–505 (2005)
Könemann, J., Parekh, O., Pritchard, D.: Max-weight integral multicommodity flow in spiders and high-capacity trees. In: Proc. 6th WAOA, pp. 1–14 (2008)
Koufogiannakis, C., Young, N.E.: Distributed and parallel algorithms for weighted vertex cover and other covering problems. In: Proc. 28th PODC, pp. 171–179 (2009)
Koufogiannakis, C., Young, N.E.: Distributed fractional packing and maximum weighted b-matching via tail-recursive duality. In: Proc. 23rd DISC, pp. 221–238 (2009)
Koufogiannakis, C., Young, N.E.: Greedy δ-approximation algorithm for covering with arbitrary constraints and submodular cost. In: Proc. 36th ICALP, pp. 634–652 (2009)
Lenstra, H.: Integer programming with a fixed number of variables. Math. Oper. Res. 8, 538–548 (1983)
Lovász, L.: Submodular functions and convexity. In: Mathematical Programming: The State of the Art, pp. 235–257. Springer, Berlin (1983)
Lueker, G.S.: Two NP-complete problems in nonnegative integer programming. Tech. Rep. 178, Computer Science Laboratory, Princeton University (1975)
Pritchard, D.: Approximability of sparse integer programs. In: Proc. 17th ESA, pp. 83–94 (2009). Preliminary version at arXiv:0904.0859
Pritchard, D.: Linear programming tools & approximation algorithms for combinatorial optimization. Ph.D. thesis, University of Waterloo (2009)
Shepherd, F.B., Vetta, A.: The demand-matching problem. Math. Oper. Res. 32(3), 563–578 (2007). Preliminary version in Proc. 9th IPCO, pp. 457–474 (2002)
Singh, M.: Iterative methods in combinatorial optimization. Ph.D. thesis, Carnegie Mellon University (2008)
Srinivasan, A.: Improved approximation guarantees for packing and covering integer programs. SIAM J. Comput. 29(2), 648–670 (1999). Preliminary version in Proc. 27th STOC, pp. 268–276 (1995)
Srinivasan, A.: An extension of the Lovász Local Lemma, and its applications to integer programming. SIAM J. Comput. 36(3), 609–634 (2006). Preliminary version in Proc. 7th SODA, pp. 6–15 (1996)
Trevisan, L.: Non-approximability results for optimization problems on bounded degree instances. In: Proc. 33rd STOC, pp. 453–461 (2001)
Wolsey, L.: An analysis of the greedy algorithm for the submodular set covering problem. Combinatorica 2(4), 385–393 (1982)
Author information
Authors and Affiliations
Corresponding author
Additional information
The first author is partially supported by an NSERC post-doctoral fellowship.
Rights and permissions
About this article
Cite this article
Pritchard, D., Chakrabarty, D. Approximability of Sparse Integer Programs. Algorithmica 61, 75–93 (2011). https://doi.org/10.1007/s00453-010-9431-z
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00453-010-9431-z