{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,30]],"date-time":"2026-07-30T01:55:47Z","timestamp":1785376547229,"version":"3.55.0"},"reference-count":78,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2019,11,15]],"date-time":"2019-11-15T00:00:00Z","timestamp":1573776000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100006785","name":"Google","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100006785","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100004344","name":"Adobe Systems","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100004344","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100008536","name":"Amazon Web Services","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100008536","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CNS 1010789, CCF 1422569, CCF-1749864"],"award-info":[{"award-number":["CNS 1010789, CCF 1422569, CCF-1749864"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2020,1,31]]},"abstract":"<jats:p>\n            Column-sparse packing problems arise in several contexts in both deterministic and stochastic discrete optimization. We present two unifying ideas,\n            <jats:italic>(non-uniform) attenuation<\/jats:italic>\n            and\n            <jats:italic>multiple-chance algorithms<\/jats:italic>\n            , to obtain improved approximation algorithms for some well-known families of such problems. As three main examples, we attain the integrality gap, up to lower-order terms, for known LP relaxations for\n            <jats:italic>k<\/jats:italic>\n            -column-sparse packing integer programs (Bansal et al.,\n            <jats:italic>Theory of Computing<\/jats:italic>\n            , 2012) and stochastic\n            <jats:italic>k<\/jats:italic>\n            -set packing (Bansal et al.,\n            <jats:italic>Algorithmica<\/jats:italic>\n            , 2012), and go \u201chalf the remaining distance\u201d to optimal for a major integrality-gap conjecture of F\u00fcredi, Kahn, and Seymour on hypergraph matching (\n            <jats:italic>Combinatorica<\/jats:italic>\n            , 1993).\n          <\/jats:p>","DOI":"10.1145\/3355400","type":"journal-article","created":{"date-parts":[[2019,11,15]],"date-time":"2019-11-15T21:16:57Z","timestamp":1573852617000},"page":"1-32","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Algorithms to Approximate Column-sparse Packing Problems"],"prefix":"10.1145","volume":"16","author":[{"given":"Brian","family":"Brubach","sequence":"first","affiliation":[{"name":"University of Maryland, College Park, Maryland, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Karthik A.","family":"Sankararaman","sequence":"additional","affiliation":[{"name":"University of Maryland, College Park, Maryland, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Aravind","family":"Srinivasan","sequence":"additional","affiliation":[{"name":"University of Maryland, College Park, Maryland, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Pan","family":"Xu","sequence":"additional","affiliation":[{"name":"University of Maryland, College Park and New Jersey Institute of Technology, New Jersey, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2019,11,15]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Non-negative submodular stochastic probing via stochastic contention resolution schemes. CoRR abs\/1508.07771","author":"Adamczyk Marek","year":"2015","unstructured":"Marek Adamczyk . 2015. Non-negative submodular stochastic probing via stochastic contention resolution schemes. CoRR abs\/1508.07771 ( 2015 ). Retrieved from: http:\/\/arxiv.org\/abs\/1508.07771. Marek Adamczyk. 2015. Non-negative submodular stochastic probing via stochastic contention resolution schemes. CoRR abs\/1508.07771 (2015). Retrieved from: http:\/\/arxiv.org\/abs\/1508.07771."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-48350-3_1"},{"key":"e_1_2_1_3_1","volume-title":"Proceedings of the 31st International Symposium on Theoretical Aspects of Computer Science. Leibniz Int. Proc. Inform.","volume":"25","author":"Adamczyk Marek","year":"2014","unstructured":"Marek Adamczyk , Maxim Sviridenko , and Justin Ward . 2014 . Submodular stochastic probing on matroids . In Proceedings of the 31st International Symposium on Theoretical Aspects of Computer Science. Leibniz Int. Proc. Inform. , Vol. 25 . 29--40. Marek Adamczyk, Maxim Sviridenko, and Justin Ward. 2014. Submodular stochastic probing on matroids. In Proceedings of the 31st International Symposium on Theoretical Aspects of Computer Science. Leibniz Int. Proc. Inform., Vol. 25. 29--40."},{"key":"e_1_2_1_4_1","volume-title":"Random order contention resolution schemes. Retrieved from: arXiv preprint arXiv:1804.02584","author":"Adamczyk Marek","year":"2018","unstructured":"Marek Adamczyk and Micha\u0142 W\u0142odarczyk . 2018. Random order contention resolution schemes. Retrieved from: arXiv preprint arXiv:1804.02584 ( 2018 ). Marek Adamczyk and Micha\u0142 W\u0142odarczyk. 2018. Random order contention resolution schemes. Retrieved from: arXiv preprint arXiv:1804.02584 (2018)."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(80)90030-8"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.23.3.640"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-005-1172-z"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.7"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132617"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.89"},{"key":"e_1_2_1_11_1","article-title":"A logarithmic approximation for unsplittable flow on line graphs","volume":"10","author":"Bansal Nikhil","year":"2014","unstructured":"Nikhil Bansal , Zachary Friggstad , Rohit Khandekar , and Mohammad R. Salavatipour . 2014 . A logarithmic approximation for unsplittable flow on line graphs . ACM Trans. Alg. 10 , 1 (2014), Article 1, 15. DOI:https:\/\/doi.org\/10.1145\/2532645 10.1145\/2532645 Nikhil Bansal, Zachary Friggstad, Rohit Khandekar, and Mohammad R. Salavatipour. 2014. A logarithmic approximation for unsplittable flow on line graphs. ACM Trans. Alg. 10, 1 (2014), Article 1, 15. DOI:https:\/\/doi.org\/10.1145\/2532645","journal-title":"ACM Trans. Alg."},{"key":"e_1_2_1_12_1","volume-title":"Improved algorithmic bounds for discrepancy of sparse set systems. Retrieved from: arXiv preprint arXiv:1601.03311","author":"Bansal Nikhil","year":"2016","unstructured":"Nikhil Bansal and Shashwat Garg . 2016. Improved algorithmic bounds for discrepancy of sparse set systems. Retrieved from: arXiv preprint arXiv:1601.03311 ( 2016 ). Nikhil Bansal and Shashwat Garg. 2016. Improved algorithmic bounds for discrepancy of sparse set systems. Retrieved from: arXiv preprint arXiv:1601.03311 (2016)."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.5555\/2220253.2220257"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2012.v008a024"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-012-9728-1"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-009-0088-2"},{"key":"e_1_2_1_17_1","first-page":"124","article-title":"Improved bounds in stochastic matching and optimization. In Approximation, Randomization, and Combinatorial Optimization","volume":"40","author":"Baveja Alok","year":"2015","unstructured":"Alok Baveja , Amit Chavan , Andrei Nikiforov , Aravind Srinivasan , and Pan Xu . 2015 . Improved bounds in stochastic matching and optimization. In Approximation, Randomization, and Combinatorial Optimization . Algorithms and Techniques. Leibniz Int. Proc. Inform. , Vol. 40. 124 -- 134 . Alok Baveja, Amit Chavan, Andrei Nikiforov, Aravind Srinivasan, and Pan Xu. 2015. Improved bounds in stochastic matching and optimization. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques. Leibniz Int. Proc. Inform., Vol. 40. 124--134.","journal-title":"Algorithms and Techniques. Leibniz Int. Proc. Inform."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.25.2.255.12228"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(81)90022-6"},{"key":"e_1_2_1_20_1","first-page":"178","article-title":"A d\/2 approximation for maximum weight independent set in d-claw free graphs","volume":"7","author":"Berman Piotr","year":"2000","unstructured":"Piotr Berman . 2000 . A d\/2 approximation for maximum weight independent set in d-claw free graphs . Nordic J. Comput. 7 , 3 (2000), 178 -- 184 . Piotr Berman. 2000. A d\/2 approximation for maximum weight independent set in d-claw free graphs. Nordic J. Comput. 7, 3 (2000), 178--184.","journal-title":"Nordic J. Comput."},{"key":"e_1_2_1_21_1","volume-title":"Proceedings of the 16th International Conference on Autonomous Agents and Multiagent Systems (AAMAS\u201917)","author":"Brubach Brian","year":"2017","unstructured":"Brian Brubach , Karthik Abinav Sankararaman , Aravind Srinivasan , and Pan Xu . 2017 . Attenuate locally, win globally: An attenuation-based framework for online stochastic matching with timeouts . In Proceedings of the 16th International Conference on Autonomous Agents and Multiagent Systems (AAMAS\u201917) . Brian Brubach, Karthik Abinav Sankararaman, Aravind Srinivasan, and Pan Xu. 2017. Attenuate locally, win globally: An attenuation-based framework for online stochastic matching with timeouts. In Proceedings of the 16th International Conference on Autonomous Agents and Multiagent Systems (AAMAS\u201917)."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975031.22"},{"key":"e_1_2_1_23_1","volume-title":"Constrained submodular maximization via a non-symmetric technique. Retrieved from: arXiv preprint arXiv:1611.03253","author":"Buchbinder Niv","year":"2016","unstructured":"Niv Buchbinder and Moran Feldman . 2016. Constrained submodular maximization via a non-symmetric technique. Retrieved from: arXiv preprint arXiv:1611.03253 ( 2016 ). Niv Buchbinder and Moran Feldman. 2016. Constrained submodular maximization via a non-symmetric technique. Retrieved from: arXiv preprint arXiv:1611.03253 (2016)."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973402.106"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1137\/080733991"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.10033"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.5555\/3118733.3118817"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-011-0451-5"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.2000.1155"},{"key":"e_1_2_1_30_1","unstructured":"Chandra Chekuri Alina Ene and Nitish Korula. 2009. Personal communication. http:\/\/chekuri.cs.illinois.edu\/papers\/ufp-tree-full.pdf.  Chandra Chekuri Alina Ene and Nitish Korula. 2009. Personal communication. http:\/\/chekuri.cs.illinois.edu\/papers\/ufp-tree-full.pdf."},{"key":"e_1_2_1_31_1","series-title":"Lecture Notes in Comput. Sci.","volume-title":"Approximation, Randomization, and Combinatorial Optimization","author":"Chekuri Chandra","unstructured":"Chandra Chekuri , Alina Ene , and Nitish Korula . 2009. Unsplittable flow in paths and trees and column-restricted packing integer programs . In Approximation, Randomization, and Combinatorial Optimization . Lecture Notes in Comput. Sci. , Vol. 5687 . Springer , Berlin , 42--55. DOI:https:\/\/doi.org\/10.1007\/978-3-642-03685-9_4 10.1007\/978-3-642-03685-9_4 Chandra Chekuri, Alina Ene, and Nitish Korula. 2009. Unsplittable flow in paths and trees and column-restricted packing integer programs. In Approximation, Randomization, and Combinatorial Optimization. Lecture Notes in Comput. Sci., Vol. 5687. Springer, Berlin, 42--55. DOI:https:\/\/doi.org\/10.1007\/978-3-642-03685-9_4"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/2688073.2688086"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2006.v002a007"},{"key":"e_1_2_1_34_1","article-title":"Multicommodity demand flow in a tree and packing integer programs","volume":"3","author":"Chekuri Chandra","year":"2007","unstructured":"Chandra Chekuri , Marcelo Mydlarz , and F. Bruce Shepherd . 2007 . Multicommodity demand flow in a tree and packing integer programs . ACM Trans. Alg. 3 , 3 (2007), Article 27, 23. DOI:https:\/\/doi.org\/10.1145\/1273340.1273343 10.1145\/1273340.1273343 Chandra Chekuri, Marcelo Mydlarz, and F. Bruce Shepherd. 2007. Multicommodity demand flow in a tree and packing integer programs. ACM Trans. Alg. 3, 3 (2007), Article 27, 23. DOI:https:\/\/doi.org\/10.1145\/1273340.1273343","journal-title":"ACM Trans. Alg."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.60"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1137\/110839655"},{"key":"e_1_2_1_37_1","volume-title":"Proceedings of the 16th ACM-SIAM Symposium on Discrete Algorithms. ACM","author":"Dean Brian C.","year":"2005","unstructured":"Brian C. Dean , Michel X. Goemans , and Jan Vondr\u00e1k . 2005 . Adaptivity and approximation for stochastic packing problems . In Proceedings of the 16th ACM-SIAM Symposium on Discrete Algorithms. ACM , New York, 395--404. Brian C. Dean, Michel X. Goemans, and Jan Vondr\u00e1k. 2005. Adaptivity and approximation for stochastic packing problems. In Proceedings of the 16th ACM-SIAM Symposium on Discrete Algorithms. ACM, New York, 395--404."},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1080.0330"},{"key":"e_1_2_1_39_1","volume-title":"Proceedings of the 32nd International Conference on Foundations of Software Technology and Theoretical Computer Science. Leibniz Int. Proc. Inform.","volume":"18","author":"Elbassioni Khaled","year":"2012","unstructured":"Khaled Elbassioni , Naveen Garg , Divya Gupta , Amit Kumar , Vishal Narula , and Arindam Pal . 2012 . Approximation algorithms for the unsplittable flow problem on paths and trees . In Proceedings of the 32nd International Conference on Foundations of Software Technology and Theoretical Computer Science. Leibniz Int. Proc. Inform. , Vol. 18 . 267--275. Khaled Elbassioni, Naveen Garg, Divya Gupta, Amit Kumar, Vishal Narula, and Arindam Pal. 2012. Approximation algorithms for the unsplittable flow problem on paths and trees. In Proceedings of the 32nd International Conference on Foundations of Software Technology and Theoretical Computer Science. Leibniz Int. Proc. Inform., Vol. 18. 267--275."},{"key":"e_1_2_1_40_1","volume-title":"Proceedings of the IEEE 57th Symposium on Foundations of Computer Science (FOCS\u201916)","author":"Ene Alina","unstructured":"Alina Ene and Huy L. Nguyen . 2016. Constrained submodular maximization: Beyond 1\/e . In Proceedings of the IEEE 57th Symposium on Foundations of Computer Science (FOCS\u201916) . IEEE, 248--257. Alina Ene and Huy L. Nguyen. 2016. Constrained submodular maximization: Beyond 1\/e. In Proceedings of the IEEE 57th Symposium on Foundations of Computer Science (FOCS\u201916). IEEE, 248--257."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.46"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0121195"},{"key":"e_1_2_1_43_1","volume-title":"Proceedings of the 5th Hungarian Colloquium on Combinatorics","author":"Frank A.","unstructured":"A. Frank and A. Gy\u00e1rf\u00e1s . 1978. How to orient the edges of a graph ? In Proceedings of the 5th Hungarian Colloquium on Combinatorics , Vol. I . Colloq. Math. Soc. J\u00e1nos Bolyai , Vol. 18. North-Holland, Amsterdam-New York, 353--364. A. Frank and A. Gy\u00e1rf\u00e1s. 1978. How to orient the edges of a graph? In Proceedings of the 5th Hungarian Colloquium on Combinatorics, Vol. I. Colloq. Math. Soc. J\u00e1nos Bolyai, Vol. 18. North-Holland, Amsterdam-New York, 353--364."},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01303202"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02523685"},{"key":"e_1_2_1_46_1","volume-title":"Adaptivity gaps for stochastic probing: Submodular and XOS functions. CoRR abs\/1608.00673","author":"Gupta Anupam","year":"2016","unstructured":"Anupam Gupta , Viswanath Nagarajan , and Sahil Singla . 2016. Adaptivity gaps for stochastic probing: Submodular and XOS functions. CoRR abs\/1608.00673 ( 2016 ). Retrieved from: http:\/\/arxiv.org\/abs\/1608.00673 Anupam Gupta, Viswanath Nagarajan, and Sahil Singla. 2016. Adaptivity gaps for stochastic probing: Submodular and XOS functions. CoRR abs\/1608.00673 (2016). Retrieved from: http:\/\/arxiv.org\/abs\/1608.00673"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974331.ch120"},{"key":"e_1_2_1_48_1","first-page":"258","article-title":"Discrepancy without partial colorings. In Approximation, Randomization, and Combinatorial Optimization","volume":"28","author":"Harvey Nicholas J. A.","year":"2014","unstructured":"Nicholas J. A. Harvey , Roy Schwartz , and Mohit Singh . 2014 . Discrepancy without partial colorings. In Approximation, Randomization, and Combinatorial Optimization . Leibniz Int. Proc. Inform. , Vol. 28. 258 -- 273 . Nicholas J. A. Harvey, Roy Schwartz, and Mohit Singh. 2014. Discrepancy without partial colorings. In Approximation, Randomization, and Combinatorial Optimization. Leibniz Int. Proc. Inform., Vol. 28. 258--273.","journal-title":"Leibniz Int. Proc. Inform."},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-006-0205-6"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1137\/0402008"},{"key":"e_1_2_1_52_1","volume-title":"Kolliopoulos and Clifford Stein","author":"Stavros","year":"2004","unstructured":"Stavros G. Kolliopoulos and Clifford Stein . 2004 . Approximating disjoint-path problems using packing integer programs. Math. Prog. 99, 1, Ser. A ( 2004), 63--87. DOI:https:\/\/doi.org\/10.1007\/s10107-002-0370-6 10.1007\/s10107-002-0370-6 Stavros G. Kolliopoulos and Clifford Stein. 2004. Approximating disjoint-path problems using packing integer programs. Math. Prog. 99, 1, Ser. A (2004), 63--87. DOI:https:\/\/doi.org\/10.1007\/s10107-002-0370-6"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(03)00351-X"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2004.07.006"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973068.60"},{"key":"e_1_2_1_56_1","article-title":"\/10. Maximizing nonmonotone submodular functions under matroid or knapsack constraints","volume":"23","author":"Lee Jon","year":"2009","unstructured":"Jon Lee , Vahab S. Mirrokni , Viswanath Nagarajan , and Maxim Sviridenko . 2009 \/10. Maximizing nonmonotone submodular functions under matroid or knapsack constraints . SIAM J. Disc. Math. 23 , 4 (2009\/10), 2053--2078. DOI:https:\/\/doi.org\/10.1137\/090750020 10.1137\/090750020 Jon Lee, Vahab S. Mirrokni, Viswanath Nagarajan, and Maxim Sviridenko. 2009\/10. Maximizing nonmonotone submodular functions under matroid or knapsack constraints. SIAM J. Disc. Math. 23, 4 (2009\/10), 2053--2078. DOI:https:\/\/doi.org\/10.1137\/090750020","journal-title":"SIAM J. Disc. Math."},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700379760"},{"key":"e_1_2_1_58_1","volume-title":"Deterministic discrepancy minimization via the multiplicative weight update method. Retrieved from: arXiv preprint arXiv:1611.08752","author":"Levy Avi","year":"2016","unstructured":"Avi Levy , Harishchandra Ramadas , and Thomas Rothvoss . 2016. Deterministic discrepancy minimization via the multiplicative weight update method. Retrieved from: arXiv preprint arXiv:1611.08752 ( 2016 ). Avi Levy, Harishchandra Ramadas, and Thomas Rothvoss. 2016. Deterministic discrepancy minimization via the multiplicative weight update method. Retrieved from: arXiv preprint arXiv:1611.08752 (2016)."},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488731"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1137\/130929400"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1112\/jlms\/s1-39.1.12"},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973082.83"},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793250767"},{"key":"e_1_2_1_64_1","series-title":"Lecture Notes in Computer Science","volume-title":"Integer Programming and Combinatorial Optimization","author":"Parekh Ojas","unstructured":"Ojas Parekh . 2011. Iterative packing for demand and hypergraph matching . In Integer Programming and Combinatorial Optimization . Lecture Notes in Computer Science , Vol. 6655 . Springer , Heidelberg , 349--361. DOI:https:\/\/doi.org\/10.1007\/978-3-642-20807-2_28 10.1007\/978-3-642-20807-2_28 Ojas Parekh. 2011. Iterative packing for demand and hypergraph matching. In Integer Programming and Combinatorial Optimization. Lecture Notes in Computer Science, Vol. 6655. Springer, Heidelberg, 349--361. DOI:https:\/\/doi.org\/10.1007\/978-3-642-20807-2_28"},{"key":"e_1_2_1_65_1","series-title":"Lecture Notes in Computer Science","volume-title":"Approximation and Online Algorithms","author":"Parekh Ojas","unstructured":"Ojas Parekh and David Pritchard . 2015. Generalized hypergraph matching via iterated packing and local ratio . In Approximation and Online Algorithms . Lecture Notes in Computer Science , Vol. 8952 . Springer , Cham , 207--223. DOI:https:\/\/doi.org\/10.1007\/978-3-319-18263-6_18 10.1007\/978-3-319-18263-6_18 Ojas Parekh and David Pritchard. 2015. Generalized hypergraph matching via iterated packing and local ratio. In Approximation and Online Algorithms. Lecture Notes in Computer Science, Vol. 8952. Springer, Cham, 207--223. DOI:https:\/\/doi.org\/10.1007\/978-3-319-18263-6_18"},{"key":"e_1_2_1_66_1","volume-title":"Proceedings of the 8th Innovations in Theoretical Computer Science Conference.","author":"Peres Yuval","year":"2017","unstructured":"Yuval Peres , Mohit Singh , and Nisheeth Vishnoi . 2017 . Random walks in polytopes and negative dependence . In Proceedings of the 8th Innovations in Theoretical Computer Science Conference. Yuval Peres, Mohit Singh, and Nisheeth Vishnoi. 2017. Random walks in polytopes and negative dependence. In Proceedings of the 8th Innovations in Theoretical Computer Science Conference."},{"key":"e_1_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230120206"},{"key":"e_1_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-04128-0_8"},{"key":"e_1_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.5555\/2616915.2616939"},{"key":"e_1_2_1_70_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0195-6698(85)80023-8"},{"key":"e_1_2_1_71_1","doi-asserted-by":"publisher","DOI":"10.1137\/141000282"},{"key":"e_1_2_1_72_1","doi-asserted-by":"publisher","DOI":"10.1137\/S089548019223872X"},{"key":"e_1_2_1_73_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1997.646130"},{"key":"e_1_2_1_74_1","volume-title":"Proceedings of the 8th ACM-SIAM Symposium on Discrete Algorithms. ACM","author":"Srinivasan Aravind","year":"1997","unstructured":"Aravind Srinivasan . 1997 . Improving the discrepancy bound for sparse matrices: Better approximations for sparse lattice approximation problems . In Proceedings of the 8th ACM-SIAM Symposium on Discrete Algorithms. ACM , New York, 692--701. Aravind Srinivasan. 1997. Improving the discrepancy bound for sparse matrices: Better approximations for sparse lattice approximation problems. In Proceedings of the 8th ACM-SIAM Symposium on Discrete Algorithms. ACM, New York, 692--701."},{"key":"e_1_2_1_75_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796314240"},{"key":"e_1_2_1_76_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0021-9800(68)80081-X"},{"key":"e_1_2_1_77_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374389"},{"key":"e_1_2_1_78_1","volume-title":"Proceedings of the 29th International Symposium on Theoretical Aspects of Computer Science. 42--53","author":"Ward Justin","year":"2012","unstructured":"Justin Ward . 2012 . A (k + 3)\/2-approximation algorithm for monotone submodular k-set packing and general k-exchange systems . In Proceedings of the 29th International Symposium on Theoretical Aspects of Computer Science. 42--53 . Justin Ward. 2012. A (k + 3)\/2-approximation algorithm for monotone submodular k-set packing and general k-exchange systems. In Proceedings of the 29th International Symposium on Theoretical Aspects of Computer Science. 42--53."},{"key":"e_1_2_1_79_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2007.v003a006"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3355400","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3355400","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3355400","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:23:34Z","timestamp":1750202614000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3355400"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,11,15]]},"references-count":78,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2020,1,31]]}},"alternative-id":["10.1145\/3355400"],"URL":"https:\/\/doi.org\/10.1145\/3355400","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,11,15]]},"assertion":[{"value":"2018-03-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-07-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-11-15","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}