{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T12:13:05Z","timestamp":1763467985399},"publisher-location":"Berlin, Heidelberg","reference-count":30,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642130359"},{"type":"electronic","value":"9783642130366"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-13036-6_28","type":"book-chapter","created":{"date-parts":[[2010,6,8]],"date-time":"2010-06-08T12:36:09Z","timestamp":1276000569000},"page":"369-382","source":"Crossref","is-referenced-by-count":26,"title":["On k-Column Sparse Packing Programs"],"prefix":"10.1007","author":[{"given":"Nikhil","family":"Bansal","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nitish","family":"Korula","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Viswanath","family":"Nagarajan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Aravind","family":"Srinivasan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"28_CR1","doi-asserted-by":"crossref","DOI":"10.1002\/9780470277331","volume-title":"The Probabilistic Method","author":"N. Alon","year":"2008","unstructured":"Alon, N., Spencer, J.: The Probabilistic Method, 3rd edn. Wiley-Interscience, New York (2008)","edition":"3"},{"key":"28_CR2","doi-asserted-by":"crossref","unstructured":"Arkin, E.M., Hassin, R.: On Local Search for Weighted k-Set Packing. In: European Symposium on Algorithms, pp. 13\u201322 (1997)","DOI":"10.1007\/3-540-63397-9_2"},{"key":"28_CR3","doi-asserted-by":"crossref","unstructured":"Austrin, P., Khot, S., Safra, S.: Inapproximability of Vertex Cover and Independent Set in Bounded Degree Graphs. In: Comp. Complexity Conference (2009)","DOI":"10.1109\/CCC.2009.38"},{"key":"28_CR4","doi-asserted-by":"crossref","unstructured":"Bansal, N., Friggstad, Z., Khandekar, R., Salavatipour, M.R.: A logarithmic approximation for unsplittable flow on line graphs. In: SODA (2009)","DOI":"10.1137\/1.9781611973068.77"},{"key":"28_CR5","doi-asserted-by":"crossref","unstructured":"Bansal, N., Korula, N., Nagarajan, V., Srinivasan, A.: On k-Column Sparse Packing Programs (full version), arXiv (2010)","DOI":"10.1007\/978-3-642-13036-6_28"},{"key":"28_CR6","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1016\/S0020-0190(00)00033-8","volume":"74","author":"A. Baveja","year":"2000","unstructured":"Baveja, A., Srinivasan, A.: Approximating Low-Congestion Routing and Column-Restricted Packing Problems. Information Proc. Letters\u00a0(74), 19\u201325 (2000)","journal-title":"Information Proc. Letters"},{"key":"28_CR7","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1287\/moor.25.2.255.12228","volume":"25","author":"A. Baveja","year":"2000","unstructured":"Baveja, A., Srinivasan, A.: Approximation Algorithms for Disjoint Paths and Related Routing and Packing Problems. Math. of Oper.\u00a0Res.\u00a0(25), 255\u2013280 (2000)","journal-title":"Math. of Oper.\u00a0Res."},{"key":"28_CR8","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0166-218X(81)90022-6","volume":"3","author":"J. Beck","year":"1981","unstructured":"Beck, J., Fiala, T.: \u201cInteger making\u201d theorems. Discrete Appl. Math.\u00a03, 1\u20138 (1981)","journal-title":"Discrete Appl. Math."},{"issue":"3","key":"28_CR9","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 Journal of Computing\u00a07(3), 178\u2013184 (2000)","journal-title":"Nordic Journal of Computing"},{"key":"28_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"182","DOI":"10.1007\/978-3-540-72792-7_15","volume-title":"Integer Programming and Combinatorial Optimization","author":"G. Calinescu","year":"2007","unstructured":"Calinescu, G., Chekuri, C., P\u00e1l, M., Vondr\u00e1k, J.: Maximizing a monotone submodular function under a matroid constraint. In: Fischetti, M., Williamson, D.P. (eds.) IPCO 2007. LNCS, vol.\u00a04513, pp. 182\u2013196. Springer, Heidelberg (2007)"},{"key":"28_CR11","unstructured":"Chakrabarty, D., Pritchard, D.: Personal Communication (2009)"},{"key":"28_CR12","unstructured":"Chandra, B., Halld\u00f3rsson, M.: Greedy Local Improvement and Weighted Packing Approximation. In: SODA (1999)"},{"key":"28_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"42","DOI":"10.1007\/978-3-642-03685-9_4","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"C. Chekuri","year":"2009","unstructured":"Chekuri, C., Ene, A., Korula, N.: Unsplittable Flow in Paths and Trees and Column-Restricted Packing Integer Programs. In: Dinur, I., Jansen, K., Naor, J., Rolim, J. (eds.) APPROX and RANDOM 2009. LNCS, vol.\u00a05687, pp. 42\u201355. Springer, Heidelberg (2009)"},{"key":"28_CR14","unstructured":"Chekuri, C., Ene, A., Korula, N.: Personal Communication (2009)"},{"key":"28_CR15","doi-asserted-by":"crossref","unstructured":"Chekuri, C., Mydlarz, M., Shepherd, B.: Multicommodity Demand Flow in a Tree and Packing Integer Programs. ACM Trans. on Algorithms\u00a03(3) (2007)","DOI":"10.1145\/1273340.1273343"},{"key":"28_CR16","doi-asserted-by":"crossref","unstructured":"Feige, U.: On maximizing welfare when utility functions are subadditive. In: STOC, pp. 41\u201350 (2006)","DOI":"10.1145\/1132516.1132523"},{"issue":"5","key":"28_CR17","doi-asserted-by":"publisher","first-page":"1608","DOI":"10.1137\/S0097539700381097","volume":"31","author":"E. Halperin","year":"2002","unstructured":"Halperin, E.: Improved Approximation Algorithms for the Vertex Cover Problem in Graphs and Hypergraphs. SIAM J. Comput.\u00a031(5), 1608\u20131623 (2002)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"28_CR18","doi-asserted-by":"publisher","first-page":"20","DOI":"10.1007\/s00037-006-0205-6","volume":"15","author":"E. Hazan","year":"2003","unstructured":"Hazan, E., Safra, S., Schwartz, O.: On the complexity of approximating k-set packing. Computational Complexity\u00a015(1), 20\u201339 (2003)","journal-title":"Computational Complexity"},{"issue":"1","key":"28_CR19","doi-asserted-by":"publisher","first-page":"68","DOI":"10.1137\/0402008","volume":"2","author":"A.J. Hurkens","year":"1989","unstructured":"Hurkens, 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.\u00a02(1), 68\u201372 (1989)","journal-title":"SIAM J. Discrete Math."},{"key":"28_CR20","doi-asserted-by":"crossref","unstructured":"Khot, S.: On the power of unique 2-prover 1-round games. In: STOC, pp. 767\u2013775 (2002)","DOI":"10.1145\/509907.510017"},{"key":"28_CR21","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1007\/s10107-002-0370-6","volume":"99","author":"S. Kolliopoulos","year":"2004","unstructured":"Kolliopoulos, S., Stein, C.: Approximating Disjoint-Path Problems using Packing Integer Programs. Mathematical Programming A\u00a0(99), 63\u201387 (2004)","journal-title":"Mathematical Programming A"},{"key":"28_CR22","doi-asserted-by":"crossref","unstructured":"Kulik, A., Shachnai, H., Tamir, T.: Maximizing submodular functions subject to multiple linear constraints. In: SODA (2009)","DOI":"10.1137\/1.9781611973068.60"},{"key":"28_CR23","doi-asserted-by":"crossref","unstructured":"Lee, J., Mirrokni, V., Nagarajan, V., Sviridenko, M.: Non-monotone submodular maximization under matroid and knapsack constraints. In: STOC, pp. 323\u2013332 (2009)","DOI":"10.1145\/1536414.1536459"},{"key":"28_CR24","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1007\/BFb0121195","volume":"8","author":"G.L. Nemhauser","year":"1978","unstructured":"Nemhauser, G.L., Wolsey, L.A., Fisher, M.L.: An analysis of approximations for maximizing submodular set functions II. Math. Prog. Study\u00a08, 73\u201387 (1978)","journal-title":"Math. Prog. Study"},{"key":"28_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1007\/978-3-642-04128-0_8","volume-title":"Algorithms - ESA 2009","author":"D. Pritchard","year":"2009","unstructured":"Pritchard, D.: Approximability of Sparse Integer Programs. In: Fiat, A., Sanders, P. (eds.) ESA 2009. LNCS, vol.\u00a05757, pp. 83\u201394. Springer, Heidelberg (2009)"},{"key":"28_CR26","doi-asserted-by":"publisher","first-page":"563","DOI":"10.1287\/moor.1070.0254","volume":"32","author":"B. Shepherd","year":"2007","unstructured":"Shepherd, B., Vetta, A.: The demand matching problem. Mathematics of Operations Research\u00a032, 563\u2013578 (2007)","journal-title":"Mathematics of Operations Research"},{"issue":"2","key":"28_CR27","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)","journal-title":"SIAM J. Comput."},{"key":"28_CR28","unstructured":"Srinivasan, A.: New approaches to covering and packing problems. In: SODA, pp. 567\u2013576 (2001)"},{"key":"28_CR29","doi-asserted-by":"crossref","unstructured":"Vondr\u00e1k, J.: Optimal approximation for the submodular welfare problem in the value oracle model. In: STOC, pp. 67\u201374 (2008)","DOI":"10.1145\/1374376.1374389"},{"issue":"1","key":"28_CR30","doi-asserted-by":"publisher","first-page":"103","DOI":"10.4086\/toc.2007.v003a006","volume":"3","author":"D. Zuckerman","year":"2007","unstructured":"Zuckerman, D.: Linear Degree Extractors and the Inapproximability of Max Clique and Chromatic Number. Theory of Computing\u00a03(1), 103\u2013128 (2007)","journal-title":"Theory of Computing"}],"container-title":["Lecture Notes in Computer Science","Integer Programming and Combinatorial Optimization"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-13036-6_28.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,24]],"date-time":"2020-11-24T03:00:23Z","timestamp":1606186823000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-13036-6_28"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642130359","9783642130366"],"references-count":30,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-13036-6_28","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}