{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:41:36Z","timestamp":1740109296695,"version":"3.37.3"},"reference-count":23,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2020,2,13]],"date-time":"2020-02-13T00:00:00Z","timestamp":1581552000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,2,13]],"date-time":"2020-02-13T00:00:00Z","timestamp":1581552000000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1526799"],"award-info":[{"award-number":["CCF-1526799"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2020,9]]},"DOI":"10.1007\/s10107-020-01472-7","type":"journal-article","created":{"date-parts":[[2020,2,13]],"date-time":"2020-02-13T06:41:16Z","timestamp":1581576076000},"page":"195-214","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["$$\\ell _1$$-Sparsity approximation bounds for packing integer programs"],"prefix":"10.1007","volume":"183","author":[{"given":"Chandra","family":"Chekuri","sequence":"first","affiliation":[]},{"given":"Kent","family":"Quanrud","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0919-4062","authenticated-orcid":false,"given":"Manuel R.","family":"Torres","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,2,13]]},"reference":[{"issue":"24","key":"1472_CR1","doi-asserted-by":"publisher","first-page":"533","DOI":"10.4086\/toc.2012.v008a024","volume":"8","author":"N Bansal","year":"2012","unstructured":"Bansal, N., Korula, N., Nagarajan, V., Srinivasan, A.: Solving packing integer programs via randomized rounding with alterations. Theory Comput. 8(24), 533\u2013565 (2012). https:\/\/doi.org\/10.4086\/toc.2012.v008a024","journal-title":"Theory Comput."},{"issue":"3","key":"1472_CR2","doi-asserted-by":"crossref","first-page":"988","DOI":"10.1287\/moor.2018.0955","volume":"44","author":"N Buchbinder","year":"2019","unstructured":"Buchbinder, N., Feldman, M.: Constrained submodular maximization via a nonsymmetric technique. Math. Oper. Res. 44(3), 988\u20131005 (2019)","journal-title":"Math. Oper. Res."},{"unstructured":"Chan, T.M.: Approximation schemes for 0\u20131 knapsack. In: 1st Symposium on Simplicity in Algorithms (2018)","key":"1472_CR3"},{"issue":"4","key":"1472_CR4","doi-asserted-by":"crossref","first-page":"837","DOI":"10.1137\/S0097539799356265","volume":"33","author":"C Chekuri","year":"2004","unstructured":"Chekuri, C., Khanna, S.: On multidimensional packing problems. SIAM J. Comput. 33(4), 837\u2013851 (2004)","journal-title":"SIAM J. Comput."},{"doi-asserted-by":"crossref","unstructured":"Chekuri, C., Quanrud, K.: On approximating (sparse) covering integer programs. In: Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1596\u20131615. SIAM (2019)","key":"1472_CR5","DOI":"10.1137\/1.9781611975482.97"},{"doi-asserted-by":"crossref","unstructured":"Chekuri, C., Vondrak, J., Zenklusen, R.: Dependent randomized rounding via exchange properties of combinatorial structures. In: 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, pp. 575\u2013584. IEEE (2010)","key":"1472_CR6","DOI":"10.1109\/FOCS.2010.60"},{"doi-asserted-by":"crossref","unstructured":"Chekuri, C., Vondr\u00e1k, J., Zenklusen, R.: Multi-budgeted matchings and matroid intersection via dependent rounding. In: Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1080\u20131097. SIAM (2011)","key":"1472_CR7","DOI":"10.1137\/1.9781611973082.82"},{"issue":"6","key":"1472_CR8","doi-asserted-by":"crossref","first-page":"1831","DOI":"10.1137\/110839655","volume":"43","author":"C Chekuri","year":"2014","unstructured":"Chekuri, C., Vondr\u00e1k, J., Zenklusen, R.: Submodular function maximization via the multilinear relaxation and contention resolution schemes. SIAM J. Comput. 43(6), 1831\u20131879 (2014)","journal-title":"SIAM J. Comput."},{"doi-asserted-by":"crossref","unstructured":"Chen, A., Harris, D.G., Srinivasan, A.: Partial resampling to approximate covering integer programs. In: Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1984\u20132003. SIAM (2016)","key":"1472_CR9","DOI":"10.1137\/1.9781611974331.ch139"},{"doi-asserted-by":"crossref","unstructured":"Ene, A., Nguyen, H.L.: Constrained submodular maximization: beyond 1\/e. In: 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), pp. 248\u2013257. IEEE (2016)","key":"1472_CR10","DOI":"10.1109\/FOCS.2016.34"},{"doi-asserted-by":"crossref","unstructured":"Feldman, M., Naor, J., Schwartz, R.: A unified continuous greedy algorithm for submodular maximization. In: 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, pp. 570\u2013579. IEEE (2011)","key":"1472_CR11","DOI":"10.1109\/FOCS.2011.46"},{"issue":"1","key":"1472_CR12","doi-asserted-by":"crossref","first-page":"100","DOI":"10.1016\/0377-2217(84)90053-5","volume":"15","author":"A Frieze","year":"1984","unstructured":"Frieze, A., Clarke, M.: Approximation algorithms for the m-dimensional 0\u20131 knapsack problem: worst-case and probabilistic analyses. Eur. J. Oper. Res. 15(1), 100\u2013109 (1984)","journal-title":"Eur. J. Oper. Res."},{"issue":"4","key":"1472_CR13","doi-asserted-by":"crossref","first-page":"517","DOI":"10.1016\/j.disc.2014.11.020","volume":"338","author":"NJ Harvey","year":"2015","unstructured":"Harvey, N.J.: A note on the discrepancy of matrices with bounded row and column sums. Discrete Math. 338(4), 517\u2013521 (2015)","journal-title":"Discrete Math."},{"issue":"1","key":"1472_CR14","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1007\/BF02392825","volume":"182","author":"J H\u00e5stad","year":"1999","unstructured":"H\u00e5stad, J.: Clique is hard to approximate within $$n^{1- \\epsilon }$$. Acta Math. 182(1), 105\u2013142 (1999)","journal-title":"Acta Math."},{"issue":"1","key":"1472_CR15","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)","journal-title":"Comput. Complex."},{"key":"1472_CR16","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511813603","volume-title":"Probability and Computing: Randomized Algorithms and Probabilistic Analysis","author":"M Mitzenmacher","year":"2005","unstructured":"Mitzenmacher, M., Upfal, E.: Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press, Cambridge (2005)"},{"doi-asserted-by":"crossref","unstructured":"Pritchard, D.: Approximability of sparse integer programs. In: European Symposium on Algorithms, pp. 83\u201394. Springer (2009)","key":"1472_CR17","DOI":"10.1007\/978-3-642-04128-0_8"},{"issue":"1","key":"1472_CR18","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1007\/s00453-010-9431-z","volume":"61","author":"D Pritchard","year":"2011","unstructured":"Pritchard, D., Chakrabarty, D.: Approximability of sparse integer programs. Algorithmica 61(1), 75\u201393 (2011)","journal-title":"Algorithmica"},{"issue":"4","key":"1472_CR19","doi-asserted-by":"crossref","first-page":"365","DOI":"10.1007\/BF02579324","volume":"7","author":"P Raghavan","year":"1987","unstructured":"Raghavan, P., Thompson, C.D.: Randomized rounding: a technique for provably good algorithms and algorithmic proofs. Combinatorica 7(4), 365\u2013374 (1987)","journal-title":"Combinatorica"},{"issue":"2","key":"1472_CR20","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)","journal-title":"SIAM J. Comput."},{"doi-asserted-by":"crossref","unstructured":"Trevisan, L.: Non-approximability results for optimization problems on bounded degree instances. In: Proceedings of the Thirty-Third Annual ACM Symposium on Theory of Computing, pp. 453\u2013461. ACM (2001)","key":"1472_CR21","DOI":"10.1145\/380752.380839"},{"doi-asserted-by":"crossref","unstructured":"Vondr\u00e1k, J.: Optimal approximation for the submodular welfare problem in the value oracle model. In: Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing, pp. 67\u201374. ACM (2008)","key":"1472_CR22","DOI":"10.1145\/1374376.1374389"},{"doi-asserted-by":"crossref","unstructured":"Zuckerman, D.: Linear degree extractors and the inapproximability of max clique and chromatic number. In: Proceedings of the Thirty-Eighth Annual ACM Symposium on Theory of Computing, pp. 681\u2013690. ACM (2006)","key":"1472_CR23","DOI":"10.1145\/1132516.1132612"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-020-01472-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10107-020-01472-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-020-01472-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,2,12]],"date-time":"2021-02-12T00:51:28Z","timestamp":1613091088000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10107-020-01472-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,2,13]]},"references-count":23,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2020,9]]}},"alternative-id":["1472"],"URL":"https:\/\/doi.org\/10.1007\/s10107-020-01472-7","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"type":"print","value":"0025-5610"},{"type":"electronic","value":"1436-4646"}],"subject":[],"published":{"date-parts":[[2020,2,13]]},"assertion":[{"value":"31 May 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 January 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 February 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}