{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,16]],"date-time":"2026-01-16T03:03:37Z","timestamp":1768532617248,"version":"3.49.0"},"reference-count":41,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2010,7,21]],"date-time":"2010-07-21T00:00:00Z","timestamp":1279670400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2011,9]]},"DOI":"10.1007\/s00453-010-9431-z","type":"journal-article","created":{"date-parts":[[2010,7,20]],"date-time":"2010-07-20T16:39:16Z","timestamp":1279643956000},"page":"75-93","source":"Crossref","is-referenced-by-count":19,"title":["Approximability of Sparse Integer Programs"],"prefix":"10.1007","volume":"61","author":[{"given":"David","family":"Pritchard","sequence":"first","affiliation":[]},{"given":"Deeparnab","family":"Chakrabarty","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2010,7,21]]},"reference":[{"key":"9431_CR1","unstructured":"Bansal, N., Korula, N., Nagarajan, V., Srinivasan, A.: On k-column sparse packing programs. In: Proc. 14th IPCO, pp. 369\u2013382 (2010). Preliminary version at arXiv:0908.2256"},{"key":"9431_CR2","doi-asserted-by":"crossref","first-page":"198","DOI":"10.1016\/0196-6774(81)90020-1","volume":"2","author":"R. Bar-Yehuda","year":"1981","unstructured":"Bar-Yehuda, R., Even, S.: A linear time approximation algorithm for the weighted vertex cover problem. J. Algorithms 2, 198\u2013203 (1981)","journal-title":"J. Algorithms"},{"issue":"4","key":"9431_CR3","doi-asserted-by":"crossref","first-page":"595","DOI":"10.1007\/s004530010075","volume":"29","author":"R. Bar-Yehuda","year":"2001","unstructured":"Bar-Yehuda, R., Rawitz, D.: Efficient algorithms for integer programs with two variables per constraint. Algorithmica 29(4), 595\u2013609 (2001)","journal-title":"Algorithmica"},{"issue":"3","key":"9431_CR4","first-page":"178","volume":"7","author":"P. Berman","year":"2000","unstructured":"Berman, P.: A d\/2 approximation for maximum weight independent set in d-claw free graphs. Nord. J. Comput. 7(3), 178\u2013184 (2000). Preliminary version in Proc. 7th SWAT, pp.\u00a0214\u2013219 (2000)","journal-title":"Nord. J. Comput."},{"key":"9431_CR5","unstructured":"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\u2013115 (2000)"},{"key":"9431_CR6","doi-asserted-by":"crossref","unstructured":"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\u2013696 (2008)","DOI":"10.1109\/FOCS.2008.47"},{"issue":"3","key":"9431_CR7","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1145\/1273340.1273343","volume":"3","author":"C. Chekuri","year":"2007","unstructured":"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.\u00a0410\u2013425 (2003)","journal-title":"ACM Trans. Algorithms"},{"key":"9431_CR8","doi-asserted-by":"crossref","unstructured":"Chekuri, C., Ene, A., Korula, N.: Unsplittable flow in paths and trees and column-restricted packing integer programs. In: Proc. 12th APPROX, pp. 42\u201355 (2009)","DOI":"10.1007\/978-3-642-03685-9_4"},{"issue":"5","key":"9431_CR9","doi-asserted-by":"crossref","first-page":"1129","DOI":"10.1137\/S0097539704443057","volume":"34","author":"I. Dinur","year":"2005","unstructured":"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\u20131146 (2005). Preliminary version in Proc. 35th STOC, pp.\u00a0595\u2013601 (2003)","journal-title":"SIAM J. Comput."},{"key":"9431_CR10","doi-asserted-by":"crossref","unstructured":"Fujito, T., Yabuta, T.: Submodular integer cover and its application to production planning. In: Proc. 2nd WAOA, pp. 154\u2013166 (2004)","DOI":"10.1007\/978-3-540-31833-0_14"},{"issue":"1","key":"9431_CR11","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1007\/BF02523685","volume":"18","author":"N. Garg","year":"1997","unstructured":"Garg, N., Vazirani, V.V., Yannakakis, M.: Primal-dual approximation algorithms for integral flow and multicut in trees. Algorithmica 18(1), 3\u201320 (1997). Preliminary version in Proc. 20th ICALP, pp.\u00a064\u201375 (1993)","journal-title":"Algorithmica"},{"key":"9431_CR12","doi-asserted-by":"crossref","unstructured":"Goel, G., Karande, C., Tripathi, P., Wang, L.: Approximability of combinatorial problems with multi-agent submodular cost functions. In: Proc. 50th FOCS, pp. 755\u2013764 (2009)","DOI":"10.1109\/FOCS.2009.81"},{"key":"9431_CR13","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-97881-4","volume-title":"Geometric Algorithms and Combinatorial Optimization","author":"M. Gr\u00f6tschel","year":"1988","unstructured":"Gr\u00f6tschel, M., Lov\u00e1sz, L., Schrijver, A.: Geometric Algorithms and Combinatorial Optimization. Springer, Berlin (1988)"},{"issue":"1","key":"9431_CR14","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1016\/0166-218X(86)90016-8","volume":"15","author":"N.G. Hall","year":"1986","unstructured":"Hall, N.G., Hochbaum, D.S.: A fast approximation algorithm for the multicovering problem. Discrete Appl. Math. 15(1), 35\u201340 (1986)","journal-title":"Discrete Appl. Math."},{"issue":"4","key":"9431_CR15","doi-asserted-by":"crossref","first-page":"798","DOI":"10.1145\/502090.502098","volume":"48","author":"J. H\u00e5stad","year":"2001","unstructured":"H\u00e5stad, J.: Some optimal inapproximability results. J. ACM 48(4), 798\u2013859 (2001)","journal-title":"J. ACM"},{"issue":"1","key":"9431_CR16","doi-asserted-by":"crossref","first-page":"20","DOI":"10.1007\/s00037-006-0205-6","volume":"15","author":"E. Hazan","year":"2006","unstructured":"Hazan, E., Safra, S., Schwartz, O.: On the complexity of approximating k-set packing. Comput. Complex. 15(1), 20\u201339 (2006). Preliminary versions in Proc. 6th APPROX, pp.\u00a083\u201397 (2003)","journal-title":"Comput. Complex."},{"key":"9431_CR17","doi-asserted-by":"crossref","first-page":"555","DOI":"10.1137\/0211045","volume":"11","author":"D.S. Hochbaum","year":"1982","unstructured":"Hochbaum, D.S.: Approximation algorithms for set covering and vertex cover problems. SIAM J. Comput. 11, 555\u2013556 (1982)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"9431_CR18","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1016\/S0167-6377(03)00074-9","volume":"32","author":"D.S. Hochbaum","year":"2004","unstructured":"Hochbaum, D.S.: Monotonizing linear programs with up to two nonzeroes per column. Oper. Res. Lett. 32(1), 49\u201358 (2004)","journal-title":"Oper. Res. Lett."},{"issue":"1","key":"9431_CR19","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1007\/BF01585160","volume":"62","author":"D.S. Hochbaum","year":"1993","unstructured":"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\u201383 (1993)","journal-title":"Math. Program."},{"issue":"1","key":"9431_CR20","doi-asserted-by":"crossref","first-page":"68","DOI":"10.1137\/0402008","volume":"2","author":"C.A.J. Hurkens","year":"1989","unstructured":"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\u201372 (1989)","journal-title":"SIAM J. Discrete Math."},{"key":"9431_CR21","doi-asserted-by":"crossref","unstructured":"Iwata, S., Nagano, K.: Submodular function minimization under covering constraints. In: Proc. 50th FOCS, pp. 671\u2013680 (2009)","DOI":"10.1109\/FOCS.2009.31"},{"key":"9431_CR22","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-540-24777-7","volume-title":"Knapsack Problems","author":"H. Kellerer","year":"2004","unstructured":"Kellerer, H., Pferschy, U., Pisinger, D.: Knapsack Problems. Springer, Berlin (2004)"},{"key":"9431_CR23","doi-asserted-by":"crossref","unstructured":"Khot, S., Ponnuswami, A.K.: Better inapproximability results for MaxClique, Chromatic Number and Min-3Lin-Deletion. In: Proc. 33rd ICALP, pp. 226\u2013237 (2006)","DOI":"10.1007\/11786986_21"},{"issue":"3","key":"9431_CR24","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1016\/j.jcss.2007.06.019","volume":"74","author":"S. Khot","year":"2008","unstructured":"Khot, S., Regev, O.: Vertex cover might be hard to approximate to within 2\u2212\u03b5. J. Comput. Syst. Sci. 74(3), 335\u2013349 (2008). Preliminary version in Proc. 18th CCC, pp. 379\u2013386 (2003)","journal-title":"J. Comput. Syst. Sci."},{"key":"9431_CR25","doi-asserted-by":"crossref","unstructured":"Kolliopoulos, S.G., Stein, C.: Improved approximation algorithms for unsplittable flow problems. In: Proc. 38th FOCS, pp. 426\u2013436 (1997)","DOI":"10.1109\/SFCS.1997.646131"},{"issue":"4","key":"9431_CR26","doi-asserted-by":"crossref","first-page":"495","DOI":"10.1016\/j.jcss.2005.05.002","volume":"71","author":"S.G. Kolliopoulos","year":"2005","unstructured":"Kolliopoulos, S.G., Young, N.E.: Approximation algorithms for covering\/packing integer programs. J. Comput. Syst. Sci. 71(4), 495\u2013505 (2005)","journal-title":"J. Comput. Syst. Sci."},{"key":"9431_CR27","doi-asserted-by":"crossref","unstructured":"K\u00f6nemann, J., Parekh, O., Pritchard, D.: Max-weight integral multicommodity flow in spiders and high-capacity trees. In: Proc. 6th WAOA, pp. 1\u201314 (2008)","DOI":"10.1007\/978-3-540-93980-1_1"},{"key":"9431_CR28","doi-asserted-by":"crossref","unstructured":"Koufogiannakis, C., Young, N.E.: Distributed and parallel algorithms for weighted vertex cover and other covering problems. In: Proc. 28th PODC, pp. 171\u2013179 (2009)","DOI":"10.1145\/1582716.1582746"},{"key":"9431_CR29","doi-asserted-by":"crossref","unstructured":"Koufogiannakis, C., Young, N.E.: Distributed fractional packing and maximum weighted b-matching via tail-recursive duality. In: Proc. 23rd DISC, pp. 221\u2013238 (2009)","DOI":"10.1007\/978-3-642-04355-0_23"},{"key":"9431_CR30","doi-asserted-by":"crossref","unstructured":"Koufogiannakis, C., Young, N.E.: Greedy \u03b4-approximation algorithm for covering with arbitrary constraints and submodular cost. In: Proc. 36th ICALP, pp. 634\u2013652 (2009)","DOI":"10.1007\/978-3-642-02927-1_53"},{"key":"9431_CR31","doi-asserted-by":"crossref","first-page":"538","DOI":"10.1287\/moor.8.4.538","volume":"8","author":"H. Lenstra","year":"1983","unstructured":"Lenstra, H.: Integer programming with a fixed number of variables. Math. Oper. Res. 8, 538\u2013548 (1983)","journal-title":"Math. Oper. Res."},{"key":"9431_CR32","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1007\/978-3-642-68874-4_10","volume-title":"Mathematical Programming: The State of the Art","author":"L. Lov\u00e1sz","year":"1983","unstructured":"Lov\u00e1sz, L.: Submodular functions and convexity. In: Mathematical Programming: The State of the Art, pp. 235\u2013257. Springer, Berlin (1983)"},{"key":"9431_CR33","unstructured":"Lueker, G.S.: Two NP-complete problems in nonnegative integer programming. Tech. Rep. 178, Computer Science Laboratory, Princeton University (1975)"},{"key":"9431_CR34","unstructured":"Pritchard, D.: Approximability of sparse integer programs. In: Proc. 17th ESA, pp. 83\u201394 (2009). Preliminary version at arXiv:0904.0859"},{"key":"9431_CR35","unstructured":"Pritchard, D.: Linear programming tools & approximation algorithms for combinatorial optimization. Ph.D. thesis, University of Waterloo (2009)"},{"issue":"3","key":"9431_CR36","doi-asserted-by":"crossref","first-page":"563","DOI":"10.1287\/moor.1070.0254","volume":"32","author":"F.B. Shepherd","year":"2007","unstructured":"Shepherd, F.B., Vetta, A.: The demand-matching problem. Math. Oper. Res. 32(3), 563\u2013578 (2007). Preliminary version in Proc. 9th IPCO, pp.\u00a0457\u2013474 (2002)","journal-title":"Math. Oper. Res."},{"key":"9431_CR37","unstructured":"Singh, M.: Iterative methods in combinatorial optimization. Ph.D. thesis, Carnegie Mellon University (2008)"},{"issue":"2","key":"9431_CR38","doi-asserted-by":"crossref","first-page":"648","DOI":"10.1137\/S0097539796314240","volume":"29","author":"A. Srinivasan","year":"1999","unstructured":"Srinivasan, A.: Improved approximation guarantees for packing and covering integer programs. SIAM J. Comput. 29(2), 648\u2013670 (1999). Preliminary version in Proc. 27th STOC, pp.\u00a0268\u2013276 (1995)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"9431_CR39","doi-asserted-by":"crossref","first-page":"609","DOI":"10.1137\/S0097539703434620","volume":"36","author":"A. Srinivasan","year":"2006","unstructured":"Srinivasan, A.: An extension of the Lov\u00e1sz Local Lemma, and its applications to integer programming. SIAM J. Comput. 36(3), 609\u2013634 (2006). Preliminary version in Proc. 7th SODA, pp.\u00a06\u201315 (1996)","journal-title":"SIAM J. Comput."},{"key":"9431_CR40","doi-asserted-by":"crossref","unstructured":"Trevisan, L.: Non-approximability results for optimization problems on bounded degree instances. In: Proc. 33rd STOC, pp. 453\u2013461 (2001)","DOI":"10.1145\/380752.380839"},{"issue":"4","key":"9431_CR41","doi-asserted-by":"crossref","first-page":"385","DOI":"10.1007\/BF02579435","volume":"2","author":"L. Wolsey","year":"1982","unstructured":"Wolsey, L.: An analysis of the greedy algorithm for the submodular set covering problem. Combinatorica 2(4), 385\u2013393 (1982)","journal-title":"Combinatorica"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-010-9431-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-010-9431-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-010-9431-z","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,23]],"date-time":"2025-02-23T04:39:27Z","timestamp":1740285567000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-010-9431-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,7,21]]},"references-count":41,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2011,9]]}},"alternative-id":["9431"],"URL":"https:\/\/doi.org\/10.1007\/s00453-010-9431-z","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,7,21]]}}}