{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,24]],"date-time":"2026-04-24T17:11:50Z","timestamp":1777050710088,"version":"3.51.4"},"reference-count":45,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2022,6,16]],"date-time":"2022-06-16T00:00:00Z","timestamp":1655337600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,6,16]],"date-time":"2022-06-16T00:00:00Z","timestamp":1655337600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"ZJ-NSFC","award":["LD19A010001"],"award-info":[{"award-number":["LD19A010001"]}]},{"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"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1910149"],"award-info":[{"award-number":["CCF-1910149"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1318996"],"award-info":[{"award-number":["CCF-1318996"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1615845"],"award-info":[{"award-number":["CCF-1615845"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"name":"National Science Foundation China","award":["U20A2068"],"award-info":[{"award-number":["U20A2068"]}]},{"name":"National Science Foundation China","award":["11771013"],"award-info":[{"award-number":["11771013"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2022,9]]},"abstract":"Abstract<\/jats:title>We consider the problem of covering multiple submodular constraints. Given a finite ground set N<\/jats:italic>, a weight function $$w: N \\rightarrow \\mathbb {R}_+$$<\/jats:tex-math>\n \n w<\/mml:mi>\n :<\/mml:mo>\n N<\/mml:mi>\n \u2192<\/mml:mo>\n \n R<\/mml:mi>\n +<\/mml:mo>\n <\/mml:msub>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, r<\/jats:italic> monotone submodular functions $$f_1,f_2,\\ldots ,f_r$$<\/jats:tex-math>\n \n \n f<\/mml:mi>\n 1<\/mml:mn>\n <\/mml:msub>\n ,<\/mml:mo>\n \n f<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msub>\n ,<\/mml:mo>\n \u2026<\/mml:mo>\n ,<\/mml:mo>\n \n f<\/mml:mi>\n r<\/mml:mi>\n <\/mml:msub>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> over N<\/jats:italic> and requirements $$k_1,k_2,\\ldots ,k_r$$<\/jats:tex-math>\n \n \n k<\/mml:mi>\n 1<\/mml:mn>\n <\/mml:msub>\n ,<\/mml:mo>\n \n k<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msub>\n ,<\/mml:mo>\n \u2026<\/mml:mo>\n ,<\/mml:mo>\n \n k<\/mml:mi>\n r<\/mml:mi>\n <\/mml:msub>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> the goal is to find a minimum weight subset $$S \\subseteq N$$<\/jats:tex-math>\n \n S<\/mml:mi>\n \u2286<\/mml:mo>\n N<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> such that $$f_i(S) \\ge k_i$$<\/jats:tex-math>\n \n \n f<\/mml:mi>\n i<\/mml:mi>\n <\/mml:msub>\n \n (<\/mml:mo>\n S<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n \u2265<\/mml:mo>\n \n k<\/mml:mi>\n i<\/mml:mi>\n <\/mml:msub>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> for $$1 \\le i \\le r$$<\/jats:tex-math>\n \n 1<\/mml:mn>\n \u2264<\/mml:mo>\n i<\/mml:mi>\n \u2264<\/mml:mo>\n r<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. We refer to this problem as Multi-Submod-Cover<\/jats:sc> and it was recently considered by Har-Peled and Jones (Few cuts meet many point sets. CoRR. arxiv:abs1808.03260<\/jats:ext-link>Har-Peled and Jones 2018) who were motivated by an application in geometry. Even with $$r=1$$<\/jats:tex-math>\n \n r<\/mml:mi>\n =<\/mml:mo>\n 1<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>Multi-Submod-Cover<\/jats:sc> generalizes the well-known Submodular Set Cover problem (Submod-SC<\/jats:sc>), and it can also be easily reduced to Submod-SC<\/jats:sc>. A simple greedy algorithm gives an $$O(\\log (kr))$$<\/jats:tex-math>\n \n O<\/mml:mi>\n (<\/mml:mo>\n log<\/mml:mo>\n (<\/mml:mo>\n k<\/mml:mi>\n r<\/mml:mi>\n )<\/mml:mo>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> approximation where $$k = \\sum _i k_i$$<\/jats:tex-math>\n \n k<\/mml:mi>\n =<\/mml:mo>\n \n \u2211<\/mml:mo>\n i<\/mml:mi>\n <\/mml:msub>\n \n k<\/mml:mi>\n i<\/mml:mi>\n <\/mml:msub>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> and this ratio cannot be improved in the general case. In this paper, motivated by several concrete applications, we consider two ways to improve upon the approximation given by the greedy algorithm. First, we give a bicriteria approximation algorithm for Multi-Submod-Cover<\/jats:sc> that covers each constraint to within a factor of $$(1-1\/e-\\varepsilon )$$<\/jats:tex-math>\n \n (<\/mml:mo>\n 1<\/mml:mn>\n -<\/mml:mo>\n 1<\/mml:mn>\n \/<\/mml:mo>\n e<\/mml:mi>\n -<\/mml:mo>\n \u03b5<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> while incurring an approximation of $$O(\\frac{1}{\\epsilon }\\log r)$$<\/jats:tex-math>\n \n O<\/mml:mi>\n (<\/mml:mo>\n \n 1<\/mml:mn>\n \u03f5<\/mml:mi>\n <\/mml:mfrac>\n log<\/mml:mo>\n r<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> in the cost. Second, we consider the special case when each $$f_i$$<\/jats:tex-math>\n \n f<\/mml:mi>\n i<\/mml:mi>\n <\/mml:msub>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> is a obtained from a truncated coverage function and obtain an algorithm that generalizes previous work on partial set cover (Partial-SC<\/jats:sc>), covering integer programs (CIPs<\/jats:sc>) and multiple vertex cover constraints Bera et al. (Theoret Comput Sci 555:2\u20138 Bera et\u00a0al. 2014). Both these algorithms are based on mathematical programming relaxations that avoid the limitations of the greedy algorithm. We demonstrate the implications of our algorithms and related ideas to several applications ranging from geometric covering problems to clustering with outliers. Our work highlights the utility of the high-level model and the lens of submodularity in addressing this class of covering problems.<\/jats:p>","DOI":"10.1007\/s10878-022-00874-x","type":"journal-article","created":{"date-parts":[[2022,6,16]],"date-time":"2022-06-16T10:22:36Z","timestamp":1655374956000},"page":"979-1010","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":9,"title":["Algorithms for covering multiple submodular constraints and applications"],"prefix":"10.1007","volume":"44","author":[{"given":"Chandra","family":"Chekuri","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0184-5932","authenticated-orcid":false,"given":"Tanmay","family":"Inamdar","sequence":"additional","affiliation":[]},{"given":"Kent","family":"Quanrud","sequence":"additional","affiliation":[]},{"given":"Kasturi","family":"Varadarajan","sequence":"additional","affiliation":[]},{"given":"Zhao","family":"Zhang","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,6,16]]},"reference":[{"issue":"3","key":"874_CR1","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1023\/B:JOCO.0000038913.96607.c2","volume":"8","author":"AA Ageev","year":"2004","unstructured":"Ageev AA, Sviridenko MI (2004) Pipage rounding: A new method of constructing algorithms with proven performance guarantee. J Comb Optim 8(3):307\u2013328","journal-title":"J Comb Optim"},{"key":"874_CR2","doi-asserted-by":"publisher","unstructured":"Ahmadian S, Swamy C (2016) Approximation algorithms for clustering problems with lower bounds and outliers. In: 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, July 11-15, 2016, Rome, Italy, pp 69:1\u201369:15 . https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2016.69","DOI":"10.4230\/LIPIcs.ICALP.2016.69"},{"issue":"7","key":"874_CR3","doi-asserted-by":"publisher","first-page":"3248","DOI":"10.1137\/090762968","volume":"39","author":"B Aronov","year":"2010","unstructured":"Aronov B, Ezra E, Sharir M (2010) Small-Size $$\\epsilon $$-Nets for Axis-Parallel Rectangles and Boxes. SIAM J Comput 39(7):3248\u20133282. https:\/\/doi.org\/10.1137\/090762968","journal-title":"SIAM J Comput"},{"key":"874_CR4","doi-asserted-by":"publisher","unstructured":"Bar-Yehuda R (2001) Using Homogeneous Weights for Approximating the Partial Cover Problem. Journal of Algorithms 39(2):137\u2013144. https:\/\/doi.org\/10.1006\/jagm.2000.1150http:\/\/www.sciencedirect.com\/science\/article\/pii\/S0196677400911507","DOI":"10.1006\/jagm.2000.1150"},{"key":"874_CR5","unstructured":"Bera SK, Chakrabarty D, Negahbani M (2019) Fair algorithms for clustering. CoRR abs\/1901.02393. arxiv:1901.02393"},{"key":"874_CR6","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1016\/j.tcs.2014.04.006","volume":"555","author":"SK Bera","year":"2014","unstructured":"Bera SK, Gupta S, Kumar A, Roy S (2014) Approximation algorithms for the partition vertex cover problem. Theoret Comput Sci 555:2\u20138","journal-title":"Theoret Comput Sci"},{"issue":"4","key":"874_CR7","doi-asserted-by":"publisher","first-page":"463","DOI":"10.1007\/BF02570718","volume":"14","author":"H Br\u00f6nnimann","year":"1995","unstructured":"Br\u00f6nnimann H, Goodrich MT (1995) Almost Optimal Set Covers in Finite VC-Dimension. Discrete & Computational Geometry 14(4):463\u2013479. https:\/\/doi.org\/10.1007\/BF02570718","journal-title":"Discrete & Computational Geometry"},{"key":"874_CR8","doi-asserted-by":"publisher","unstructured":"Bshouty NH, Burroughs L (1998) Massaging a Linear Programming Solution to Give a 2-Approximation for a Generalization of the Vertex Cover Problem. In: STACS 98, 15th Annual Symposium on Theoretical Aspects of Computer Science, Paris, France, February 25-27, 1998, Proceedings, pp 298\u2013308 . https:\/\/doi.org\/10.1007\/BFb0028569","DOI":"10.1007\/BFb0028569"},{"key":"874_CR9","first-page":"753","volume":"1","author":"N Buchbinder","year":"2017","unstructured":"Buchbinder N, Feldman M (2017) Submodular functions maximization problems. Handb Approximation Algorithms Metaheuristics 1:753\u2013788","journal-title":"Handb Approximation Algorithms Metaheuristics"},{"key":"874_CR10","unstructured":"Byrka J, Ghodsi M, Srinivasan A (2010) Lp-rounding algorithms for facility-location problems. CoRR abs\/1007.3611. arxiv:1007.3611"},{"key":"874_CR11","doi-asserted-by":"crossref","unstructured":"Calinescu G, Chekuri C, P\u00e1l M, Vondr\u00e1k J (2007) Maximizing a submodular set function subject to a matroid constraint (extended abstract). In: Integer Programming and Combinatorial Optimization (IPCO), pp 182\u2013196","DOI":"10.1007\/978-3-540-72792-7_15"},{"issue":"6","key":"874_CR12","doi-asserted-by":"publisher","first-page":"1740","DOI":"10.1137\/080733991","volume":"40","author":"G C\u0103linescu","year":"2011","unstructured":"C\u0103linescu G, Chekuri C, P\u00e1l M, Vondr\u00e1k J (2011) Maximizing a monotone submodular function subject to a matroid constraint. SIAM J Comput 40(6):1740\u20131766","journal-title":"SIAM J Comput"},{"key":"874_CR13","unstructured":"Carr RD, Fleischer L, Leung VJ, Phillips CA (2000) Strengthening integrality gaps for capacitated network design and covering problems. In: Proceedings of ACM-SIAM SODA, pp 106\u2013115"},{"key":"874_CR14","doi-asserted-by":"crossref","unstructured":"Chan TM, Grant E, K\u00f6nemann J, Sharpe M (2012) Weighted capacitated, priority, and geometric set cover via improved quasi-uniform sampling. In: Proceedings of the twenty-third annual ACM-SIAM symposium on Discrete Algorithms, pp 1576\u20131585. Society for Industrial and Applied Mathematics","DOI":"10.1137\/1.9781611973099.125"},{"issue":"5","key":"874_CR15","doi-asserted-by":"publisher","first-page":"380","DOI":"10.1016\/j.comgeo.2014.12.005","volume":"48","author":"TM Chan","year":"2015","unstructured":"Chan TM, Hu N (2015) Geometric red-blue set cover for unit squares and related problems. Comput Geom 48(5):380\u2013385. https:\/\/doi.org\/10.1016\/j.comgeo.2014.12.005","journal-title":"Comput Geom"},{"key":"874_CR16","unstructured":"Charikar M, Khuller S, Mount DM, Narasimhan G (2001) Algorithms for facility location problems with outliers. In: Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, pp 642\u2013651. Society for Industrial and Applied Mathematics"},{"issue":"2","key":"874_CR17","doi-asserted-by":"publisher","first-page":"417","DOI":"10.1016\/j.jcss.2003.07.014","volume":"68","author":"M Charikar","year":"2004","unstructured":"Charikar M, Panigrahy R (2004) Clustering to minimize the sum of cluster diameters. J Comput Syst Sci 68(2):417\u2013441. https:\/\/doi.org\/10.1016\/j.jcss.2003.07.014","journal-title":"J Comput Syst Sci"},{"key":"874_CR18","doi-asserted-by":"crossref","unstructured":"Chekuri C, Jayram T, Vondr\u00e1k J (2015) On multiplicative weight updates for concave and submodular function maximization. In: Proceedings of ITCS","DOI":"10.1145\/2688073.2688086"},{"key":"874_CR19","doi-asserted-by":"crossref","unstructured":"Chekuri C, Quanrud K (2019) On approximating (sparse) covering integer programs. In: Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1596\u20131615. SIAM","DOI":"10.1137\/1.9781611975482.97"},{"key":"874_CR20","unstructured":"Chekuri C, Quanrud K, Zhang Z (2019) On approximating partial set cover and generalizations. CoRR arxiv:1907.04413"},{"key":"874_CR21","doi-asserted-by":"publisher","unstructured":"Chekuri C, Vondr\u00e1k J, Zenklusen R (2010) Dependent randomized rounding via exchange properties of combinatorial structures. In: 51th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2010, October 23-26, 2010, Las Vegas, Nevada, USA, pp 575\u2013584. https:\/\/doi.org\/10.1109\/FOCS.2010.60","DOI":"10.1109\/FOCS.2010.60"},{"key":"874_CR22","doi-asserted-by":"crossref","unstructured":"Chen A, Harris DG, Srinivasan A (2016) Partial resampling to approximate covering integer programs. In: Proceedings of 27th ACM-SIAM SODA, pp 1984\u20132003","DOI":"10.1137\/1.9781611974331.ch139"},{"issue":"1","key":"874_CR23","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1007\/s00454-006-1273-8","volume":"37","author":"KL Clarkson","year":"2007","unstructured":"Clarkson KL, Varadarajan K (2007) Improved Approximation Algorithms for Geometric Set Cover. Discrete & Computational Geometry 37(1):43\u201358. https:\/\/doi.org\/10.1007\/s00454-006-1273-8","journal-title":"Discrete & Computational Geometry"},{"key":"874_CR24","doi-asserted-by":"publisher","unstructured":"Dinur I, Steurer D (2014) Analytical Approach to Parallel Repetition. In: Proceedings of the Forty-sixth Annual ACM Symposium on Theory of Computing, STOC \u201914, pp. 624\u2013633. ACM, New York, NY, USA. https:\/\/doi.org\/10.1145\/2591796.2591884","DOI":"10.1145\/2591796.2591884"},{"issue":"4","key":"874_CR25","doi-asserted-by":"publisher","first-page":"515","DOI":"10.1287\/moor.7.4.515","volume":"7","author":"G Dobson","year":"1982","unstructured":"Dobson G (1982) Worst-case analysis of greedy heuristics for integer programming with nonnegative data. Math Oper Res 7(4):515\u2013531","journal-title":"Math Oper Res"},{"key":"874_CR26","doi-asserted-by":"crossref","unstructured":"Ezra E, Aronov B, Sharir M (2011) Improved Bound for the Union of Fat Triangles. In: Proceedings of the Twenty-second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA \u201911, pp 1778\u20131785. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA. http:\/\/dl.acm.org\/citation.cfm?id=2133036.2133172","DOI":"10.1137\/1.9781611973082.136"},{"issue":"1","key":"874_CR27","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1016\/j.jalgor.2004.04.002","volume":"53","author":"R Gandhi","year":"2004","unstructured":"Gandhi R, Khuller S, Srinivasan A (2004) Approximation algorithms for partial covering problems. J Algorithms 53(1):55\u201384. https:\/\/doi.org\/10.1016\/j.jalgor.2004.04.002","journal-title":"J Algorithms"},{"key":"874_CR28","doi-asserted-by":"publisher","unstructured":"Gibson M, Pirwani IA (2010) Algorithms for dominating set in disk graphs: Breaking the logn barrier - (extended abstract). In: Algorithms - ESA 2010, 18th Annual European Symposium, Liverpool, UK, September 6-8, 2010. Proceedings, Part I, pp 243\u2013254. https:\/\/doi.org\/10.1007\/978-3-642-15775-2_21","DOI":"10.1007\/978-3-642-15775-2_21"},{"key":"874_CR29","unstructured":"Har-Peled S, Jones M (2018) Few cuts meet many point sets. CoRR . arxiv:abs1808.03260"},{"key":"874_CR30","doi-asserted-by":"publisher","unstructured":"Hong E, Kao MJ (2018) Approximation Algorithm for Vertex Cover with Multiple Covering Constraints. In: Hsu WL, Lee DT, Liao CS (eds.) 29th International Symposium on Algorithms and Computation (ISAAC 2018), Leibniz International Proceedings in Informatics (LIPIcs), vol. 123, pp 43:1\u201343:11. Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany. https:\/\/doi.org\/10.4230\/LIPIcs.ISAAC.2018.43. http:\/\/drops.dagstuhl.de\/opus\/volltexte\/2018\/9991","DOI":"10.4230\/LIPIcs.ISAAC.2018.43"},{"key":"874_CR31","unstructured":"Inamdar T (2019) Local search for geometric partial covering problems. In: Proceedings of the 31st Canadian Conference on Computational Geometry, CCCG 2019, Edmonton, Alberta, Canada, August 8-10, 2019, pp 242\u2013249"},{"key":"874_CR32","doi-asserted-by":"publisher","unstructured":"Inamdar T, Varadarajan KR (2018) On partial covering for geometric set systems. In: 34th International Symposium on Computational Geometry, SoCG 2018, June 11-14, 2018, Budapest, Hungary, pp 47:1\u201347:14. https:\/\/doi.org\/10.4230\/LIPIcs.SoCG.2018.47","DOI":"10.4230\/LIPIcs.SoCG.2018.47"},{"key":"874_CR33","unstructured":"Inamdar T, Varadarajan KR (2018) On the partition set cover problem. CoRR arxiv:1809.06506"},{"issue":"1","key":"874_CR34","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1016\/S0020-0190(99)00031-9","volume":"70","author":"S Khuller","year":"1999","unstructured":"Khuller S, Moss A, Naor JS (1999) The budgeted maximum coverage problem. Inf Process Lett 70(1):39\u201345","journal-title":"Inf Process Lett"},{"issue":"4","key":"874_CR35","doi-asserted-by":"publisher","first-page":"495","DOI":"10.1016\/j.jcss.2005.05.002","volume":"71","author":"SG Kolliopoulos","year":"2005","unstructured":"Kolliopoulos SG, Young NE (2005) Approximation algorithms for covering\/packing integer programs. J Comput Syst Sci 71(4):495\u2013505 (Preliminary version in FOCS 2001)","journal-title":"J Comput Syst Sci"},{"issue":"4","key":"874_CR36","doi-asserted-by":"publisher","first-page":"489","DOI":"10.1007\/s00453-009-9317-0","volume":"59","author":"J K\u00f6nemann","year":"2011","unstructured":"K\u00f6nemann J, Parekh O, Segev D (2011) A Unified Approach to Approximating Partial Covering Problems. Algorithmica 59(4):489\u2013509. https:\/\/doi.org\/10.1007\/s00453-009-9317-0","journal-title":"Algorithmica"},{"key":"874_CR37","doi-asserted-by":"crossref","unstructured":"Mustafa NH, Raman R, Ray S (2014) Settling the APX-hardness status for geometric set cover. In: Foundations of Computer Science (FOCS), 2014 IEEE 55th Annual Symposium on, pp 541\u2013550. IEEE","DOI":"10.1109\/FOCS.2014.64"},{"issue":"1","key":"874_CR38","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1007\/BF01588971","volume":"14","author":"GL Nemhauser","year":"1978","unstructured":"Nemhauser GL, Wolsey LA, Fisher ML (1978) An analysis of approximations for maximizing submodular set functions\u2013i. Math Program 14(1):265\u2013294","journal-title":"Math Program"},{"issue":"1","key":"874_CR39","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1016\/S0167-6377(03)00062-2","volume":"32","author":"M Sviridenko","year":"2004","unstructured":"Sviridenko M (2004) A note on maximizing a submodular set function subject to a knapsack constraint. Oper Res Lett 32(1):41\u201343","journal-title":"Oper Res Lett"},{"key":"874_CR40","doi-asserted-by":"publisher","unstructured":"Varadarajan KR (2009) Epsilon nets and union complexity. In: Proceedings of the 25th ACM Symposium on Computational Geometry, Aarhus, Denmark, June 8-10, 2009, pp 11\u201316. https:\/\/doi.org\/10.1145\/1542362.1542366","DOI":"10.1145\/1542362.1542366"},{"key":"874_CR41","doi-asserted-by":"publisher","unstructured":"Varadarajan KR (2010) Weighted geometric set cover via quasi-uniform sampling. In: Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, Cambridge, Massachusetts, USA, 5-8 June 2010, pp 641\u2013648. https:\/\/doi.org\/10.1145\/1806689.1806777","DOI":"10.1145\/1806689.1806777"},{"key":"874_CR42","unstructured":"Vondr\u00e1k J (2007) Submodularity in combinatorial optimization. Ph.D. thesis, Charles University. Avaulable at https:\/\/theory.stanford.edu\/~jvondrak\/data\/KAM_thesis.pdf"},{"key":"874_CR43","doi-asserted-by":"crossref","unstructured":"Vondr\u00e1k J (2008) 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","DOI":"10.1145\/1374376.1374389"},{"key":"874_CR44","unstructured":"Vondr\u00e1k J (2010) A note on concentration of submodular functions. CoRR. arxiv:1005.2791"},{"issue":"4","key":"874_CR45","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1007\/BF02579435","volume":"2","author":"LA Wolsey","year":"1982","unstructured":"Wolsey LA (1982) An analysis of the greedy algorithm for the submodular set covering problem. Combinatorica 2(4):385\u2013393","journal-title":"Combinatorica"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-022-00874-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10878-022-00874-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-022-00874-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,8,13]],"date-time":"2022-08-13T06:14:34Z","timestamp":1660371274000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10878-022-00874-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,6,16]]},"references-count":45,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2022,9]]}},"alternative-id":["874"],"URL":"https:\/\/doi.org\/10.1007\/s10878-022-00874-x","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,6,16]]},"assertion":[{"value":"2 June 2022","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 June 2022","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors have not disclosed any competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}