{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T11:56:48Z","timestamp":1725537408023},"publisher-location":"Berlin, Heidelberg","reference-count":30,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642041273"},{"type":"electronic","value":"9783642041280"}],"license":[{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2009]]},"DOI":"10.1007\/978-3-642-04128-0_8","type":"book-chapter","created":{"date-parts":[[2009,9,14]],"date-time":"2009-09-14T14:16:36Z","timestamp":1252937796000},"page":"83-94","source":"Crossref","is-referenced-by-count":12,"title":["Approximability of Sparse Integer Programs"],"prefix":"10.1007","author":[{"given":"David","family":"Pritchard","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"8_CR1","doi-asserted-by":"publisher","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.\u00a08, 538\u2013548 (1983)","journal-title":"Math. Oper. Res."},{"issue":"5","key":"8_CR2","doi-asserted-by":"publisher","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.\u00a034(5), 1129\u20131146 (2005); Preliminary version appeared in Proc. 35th STOC, pp. 595\u2013601 (2003)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"8_CR3","doi-asserted-by":"publisher","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\u2009\u2212\u2009\u03b5. J. Comput. Syst. Sci.\u00a074(3), 335\u2013349 (2008); Preliminary version appeared in Proc. 18th CCC, pp. 379\u2013386 (2003)","journal-title":"J. Comput. Syst. Sci."},{"key":"8_CR4","doi-asserted-by":"publisher","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.\u00a011, 555\u2013556 (1982)","journal-title":"SIAM J. Comput."},{"key":"8_CR5","doi-asserted-by":"publisher","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\u00a02, 198\u2013203 (1981)","journal-title":"J. Algorithms"},{"issue":"1","key":"8_CR6","doi-asserted-by":"publisher","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.\u00a015(1), 35\u201340 (1986)","journal-title":"Discrete Appl. Math."},{"issue":"1","key":"8_CR7","doi-asserted-by":"publisher","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.\u00a062(1), 69\u201383 (1993)","journal-title":"Math. Program."},{"issue":"4","key":"8_CR8","doi-asserted-by":"publisher","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\u00a029(4), 595\u2013609 (2001)","journal-title":"Algorithmica"},{"key":"8_CR9","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":"8_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"154","DOI":"10.1007\/978-3-540-31833-0_14","volume-title":"Approximation and Online Algorithms","author":"T. Fujito","year":"2005","unstructured":"Fujito, T., Yabuta, T.: Submodular integer cover and its application to production planning. In: Persiano, G., Solis-Oba, R. (eds.) WAOA 2004. LNCS, vol.\u00a03351, pp. 154\u2013166. Springer, Heidelberg (2005)"},{"key":"8_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"634","DOI":"10.1007\/978-3-642-02927-1_53","volume-title":"ICALP 2009","author":"C. Koufogiannakis","year":"2009","unstructured":"Koufogiannakis, C., Young, N.E.: Greedy degree-approximation algorithm for covering with arbitrary constraints and submodular cost. In: Albers, S., Marchetti-Spaccamela, A., Matias, Y., Nikoletseas, S., Thomas, W. (eds.) ICALP 2009. Part I. LNCS, vol.\u00a05555, pp. 634\u2013652. Springer, Heidelberg (2009) arXiv:0807.0644"},{"key":"8_CR12","unstructured":"Pritchard, D.: Approximability of sparse integer programs (2009) arXiv:0904.0859"},{"issue":"3","key":"8_CR13","doi-asserted-by":"publisher","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. Mathematics of Operations Research\u00a032(3), 563\u2013578 (2007); Preliminary version appeared in Proc. 9th IPCO, pp. 457\u2013474, (2002)","journal-title":"Mathematics of Operations Research"},{"issue":"3","key":"8_CR14","doi-asserted-by":"publisher","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\u00a03(3), 27 (2007); Preliminary version appeared in Proc. 30th ICALP, pp. 410\u2013425 (2003)","journal-title":"ACM Trans. Algorithms"},{"issue":"3","key":"8_CR15","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. Nordic J. of Computing\u00a07(3), 178\u2013184 (2000); Preliminary version appeared in Proc. 7th SWAT, pp. 214\u2013219 (2000)","journal-title":"Nordic J. of Computing"},{"issue":"1","key":"8_CR16","doi-asserted-by":"publisher","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. Discret. Math.\u00a02(1), 68\u201372 (1989)","journal-title":"SIAM J. Discret. Math."},{"issue":"1","key":"8_CR17","doi-asserted-by":"publisher","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.\u00a015(1), 20\u201339 (2006); Preliminary versions appeared in Proc. 6th APPROX, pp. 83\u201397 (2003); ECCC-TR03-020 (2003)","journal-title":"Comput. Complex."},{"key":"8_CR18","unstructured":"Singh, M.: Iterative Methods in Combinatorial Optimization. PhD thesis, Carnegie Mellon University (2008)"},{"issue":"2","key":"8_CR19","doi-asserted-by":"publisher","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.\u00a029(2), 648\u2013670 (1999); Preliminary version appeared in Proc. 27th STOC, pp. 268\u2013276 (1995)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"8_CR20","doi-asserted-by":"publisher","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.\u00a036(3), 609\u2013634 (2006); Preliminary version appeared in Proc. 7th SODA, pp. 6\u201315 (1996)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"8_CR21","doi-asserted-by":"publisher","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.\u00a071(4), 495\u2013505 (2005)","journal-title":"J. Comput. Syst. Sci."},{"key":"8_CR22","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":"1","key":"8_CR23","doi-asserted-by":"publisher","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.\u00a032(1), 49\u201358 (2004)","journal-title":"Oper. Res. Lett."},{"key":"8_CR24","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"},{"key":"8_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"226","DOI":"10.1007\/11786986_21","volume-title":"Automata, Languages and Programming","author":"S. Khot","year":"2006","unstructured":"Khot, S., Ponnuswami, A.K.: Better inapproximability results for maxClique, chromatic number and min-3Lin-deletion. In: Bugliesi, M., Preneel, B., Sassone, V., Wegener, I. (eds.) ICALP 2006. LNCS, vol.\u00a04051, pp. 226\u2013237. Springer, Heidelberg (2006)"},{"key":"8_CR26","doi-asserted-by":"publisher","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, Heidelberg (2004)"},{"issue":"2","key":"8_CR27","doi-asserted-by":"publisher","first-page":"244","DOI":"10.1287\/moor.9.2.244","volume":"9","author":"M.J. Magazine","year":"1984","unstructured":"Magazine, M.J., Chern, M.S.: A note on approximation schemes for multidimensional knapsack problems. Math. of Oper. Research\u00a09(2), 244\u2013247 (1984)","journal-title":"Math. of Oper. Research"},{"issue":"4","key":"8_CR28","doi-asserted-by":"publisher","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\u00a02(4), 385\u2013393 (1982)","journal-title":"Combinatorica"},{"key":"8_CR29","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"},{"key":"8_CR30","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-540-93980-1_1","volume-title":"Approximation and Online Algorithms","author":"J. K\u00f6nemann","year":"2009","unstructured":"K\u00f6nemann, J., Parekh, O., Pritchard, D.: Max-weight integral multicommodity flow in spiders and high-capacity trees. In: Bampis, E., Skutella, M. (eds.) WAOA 2008. LNCS, vol.\u00a05426, pp. 1\u201314. Springer, Heidelberg (2009)"}],"container-title":["Lecture Notes in Computer Science","Algorithms - ESA 2009"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-04128-0_8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,3,9]],"date-time":"2019-03-09T14:41:39Z","timestamp":1552142499000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-04128-0_8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642041273","9783642041280"],"references-count":30,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-04128-0_8","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2009]]}}}