{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,16]],"date-time":"2026-05-16T04:48:31Z","timestamp":1778906911036,"version":"3.51.4"},"reference-count":38,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2023,1,9]],"date-time":"2023-01-09T00:00:00Z","timestamp":1673222400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,1,9]],"date-time":"2023-01-09T00:00:00Z","timestamp":1673222400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/100000083","name":"Directorate for Computer and Information Science and Engineering","doi-asserted-by":"publisher","award":["2007814"],"award-info":[{"award-number":["2007814"]}],"id":[{"id":"10.13039\/100000083","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100007297","name":"Office of Naval Research Global","doi-asserted-by":"publisher","award":["N00014-22-1-2602"],"award-info":[{"award-number":["N00014-22-1-2602"]}],"id":[{"id":"10.13039\/100007297","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2023,9]]},"DOI":"10.1007\/s10107-022-01921-5","type":"journal-article","created":{"date-parts":[[2023,1,9]],"date-time":"2023-01-09T14:04:46Z","timestamp":1673273086000},"page":"803-861","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Strong valid inequalities for a class of concave submodular minimization problems under cardinality constraints"],"prefix":"10.1007","volume":"201","author":[{"given":"Qimeng","family":"Yu","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6548-9378","authenticated-orcid":false,"given":"Simge","family":"K\u00fc\u00e7\u00fckyavuz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,1,9]]},"reference":[{"issue":"9","key":"1921_CR1","doi-asserted-by":"crossref","first-page":"e1007284","DOI":"10.1371\/journal.pcbi.1007284","volume":"15","author":"B Adhikari","year":"2019","unstructured":"Adhikari, B., Lewis, B., Vullikanti, A., Jim\u00e9nez, J.M., Prakash, B.A.: Fast and near-optimal monitoring for healthcare acquired infection outbreaks. PLoS Comput. Biol. 15(9), e1007284 (2019)","journal-title":"PLoS Comput. Biol."},{"issue":"1","key":"1921_CR2","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1007\/s10107-009-0298-1","volume":"128","author":"S Ahmed","year":"2011","unstructured":"Ahmed, S., Atamt\u00fcrk, A.: Maximizing a class of submodular utility functions. Math. Program. 128(1), 149\u2013169 (2011)","journal-title":"Math. Program."},{"issue":"2","key":"1921_CR3","first-page":"609","volume":"68","author":"A Atamt\u00fcrk","year":"2020","unstructured":"Atamt\u00fcrk, A., G\u00f3mez, A.: Submodularity in conic quadratic mixed 0\u20131 optimization. Oper. Res. 68(2), 609\u2013630 (2020)","journal-title":"Oper. Res."},{"key":"1921_CR4","unstructured":"Atamt\u00fcrk, A., G\u00f3mez, A.: Supermodularity and valid inequalities for quadratic optimization with indicators. (2020). arXiv preprint arXiv:2012.14633"},{"issue":"4","key":"1921_CR5","doi-asserted-by":"crossref","first-page":"677","DOI":"10.1007\/s10898-018-00736-z","volume":"73","author":"A Atamt\u00fcrk","year":"2019","unstructured":"Atamt\u00fcrk, A., Jeon, H.: Lifted polymatroid inequalities for mean-risk optimization with indicator variables. J. Global Optim. 73(4), 677\u2013699 (2019)","journal-title":"J. Global Optim."},{"issue":"5","key":"1921_CR6","doi-asserted-by":"crossref","first-page":"618","DOI":"10.1016\/j.orl.2008.04.006","volume":"36","author":"A Atamt\u00fcrk","year":"2008","unstructured":"Atamt\u00fcrk, A., Narayanan, V.: Polymatroids and mean-risk minimization in discrete optimization. Oper. Res. Lett. 36(5), 618\u2013622 (2008)","journal-title":"Oper. Res. Lett."},{"issue":"4","key":"1921_CR7","doi-asserted-by":"crossref","first-page":"333","DOI":"10.1016\/j.disopt.2009.03.002","volume":"6","author":"A Atamt\u00fcrk","year":"2009","unstructured":"Atamt\u00fcrk, A., Narayanan, V.: The submodular knapsack polytope. Discret. Optim. 6(4), 333\u2013344 (2009)","journal-title":"Discret. Optim."},{"issue":"1\u20132","key":"1921_CR8","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1007\/s10107-020-01607-w","volume":"196","author":"A Atamt\u00fcrk","year":"2022","unstructured":"Atamt\u00fcrk, A., Narayanan, V.: Submodular function minimization and polarity. Math. Program. 196(1\u20132), 57\u201367 (2022)","journal-title":"Math. Program."},{"key":"1921_CR9","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4614-0237-4","volume-title":"Introduction to Stochastic Programming","author":"JR Birge","year":"2011","unstructured":"Birge, J.R., Louveaux, F.: Introduction to Stochastic Programming. Springer, Berlin (2011)"},{"key":"1921_CR10","first-page":"69","volume-title":"Combinatorial Structures and Their Applications","author":"J Edmonds","year":"1970","unstructured":"Edmonds, J.: Submodular functions, matroids, and certain polyhedra. In: Guy, R., Hanani, H., Sauer, N., Sch\u00f6nheim, J. (eds.) Combinatorial Structures and Their Applications, pp. 69\u201387. Gordon and Breach, New York (1970)"},{"key":"1921_CR11","doi-asserted-by":"crossref","unstructured":"Edmonds, J.: Submodular functions, matroids, and certain polyhedra. In: Combinatorial Optimization-Eureka, You Shrink!, pp. 11\u201326. Springer (2003)","DOI":"10.1007\/3-540-36478-1_2"},{"issue":"9","key":"1921_CR12","doi-asserted-by":"crossref","first-page":"670","DOI":"10.1287\/mnsc.12.9.670","volume":"12","author":"E Feldman","year":"1966","unstructured":"Feldman, E., Lehrer, F., Ray, T.: Warehouse location under continuous economies of scale. Manage. Sci. 12(9), 670\u2013684 (1966)","journal-title":"Manage. Sci."},{"key":"1921_CR13","unstructured":"G\u00f3mez, A.: Submodularity and valid inequalities in nonlinear optimization with indicator variables. (2018). http:\/\/www.optimization-online.org\/DB_FILE\/2018\/11\/6925.pdf"},{"issue":"2","key":"1921_CR14","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1007\/BF02579273","volume":"1","author":"M Gr\u00f6tschel","year":"1981","unstructured":"Gr\u00f6tschel, M., Lov\u00e1sz, L., Schrijver, A.: The ellipsoid method and its consequences in combinatorial optimization. Combinatorica 1(2), 169\u2013197 (1981)","journal-title":"Combinatorica"},{"issue":"1","key":"1921_CR15","first-page":"42","volume":"42","author":"MT Hajiaghayi","year":"2003","unstructured":"Hajiaghayi, M.T., Mahdian, M., Mirrokni, V.S.: The facility location problem with general cost functions. Netw. Int. J. 42(1), 42\u201347 (2003)","journal-title":"Netw. Int. J."},{"issue":"2","key":"1921_CR16","doi-asserted-by":"crossref","first-page":"362","DOI":"10.1287\/moor.14.2.362","volume":"14","author":"R Hassin","year":"1989","unstructured":"Hassin, R., Tamir, A.: Maximizing classes of two-parameter objectives over matroids. Math. Oper. Res. 14(2), 362\u2013375 (1989)","journal-title":"Math. Oper. Res."},{"issue":"4","key":"1921_CR17","doi-asserted-by":"crossref","first-page":"761","DOI":"10.1145\/502090.502096","volume":"48","author":"S Iwata","year":"2001","unstructured":"Iwata, S., Fleischer, L., Fujishige, S.: A combinatorial strongly polynomial algorithm for minimizing submodular functions. J. ACM 48(4), 761\u2013777 (2001)","journal-title":"J. ACM"},{"issue":"4","key":"1921_CR18","doi-asserted-by":"crossref","first-page":"105","DOI":"10.4086\/toc.2015.v011a004","volume":"11","author":"D Kempe","year":"2015","unstructured":"Kempe, D., Kleinberg, J., Tardos, \u00c9.: Maximizing the spread of influence through a social network. Theory Comput. 11(4), 105\u2013147 (2015)","journal-title":"Theory Comput."},{"key":"1921_CR19","unstructured":"K\u0131l\u0131n\u00e7-Karzan, F., K\u00fc\u00e7\u00fckyavuz, S., Lee, D.: Conic mixed-binary sets: Convex hull characterizations and applications. (2020). arXiv preprint arXiv:2012.14698"},{"issue":"1\u20132","key":"1921_CR20","doi-asserted-by":"crossref","first-page":"283","DOI":"10.1007\/s10107-021-01688-1","volume":"195","author":"F K\u0131l\u0131n\u00e7-Karzan","year":"2022","unstructured":"K\u0131l\u0131n\u00e7-Karzan, F., K\u00fc\u00e7\u00fckyavuz, S., Lee, D.: Joint chance-constrained programs and the intersection of mixing sets through a submodularity lens. Math. Program. 195(1\u20132), 283\u2013326 (2022)","journal-title":"Math. Program."},{"issue":"6","key":"1921_CR21","doi-asserted-by":"crossref","first-page":"516","DOI":"10.1061\/(ASCE)0733-9496(2008)134:6(516)","volume":"134","author":"A Krause","year":"2008","unstructured":"Krause, A., Leskovec, J., Guestrin, C., VanBriesen, J., Faloutsos, C.: Efficient sensor placement optimization for securing large water distribution networks. J. Water Resour. Plan. Manag. 134(6), 516\u2013526 (2008)","journal-title":"J. Water Resour. Plan. Manag."},{"key":"1921_CR22","doi-asserted-by":"crossref","unstructured":"Lee, Y.T., Sidford, A., Wong, S.C.-w.: A faster cutting plane method and its implications for combinatorial and convex optimization. In: 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, pp. 1049\u20131065. IEEE (2015)","DOI":"10.1109\/FOCS.2015.68"},{"key":"1921_CR23","doi-asserted-by":"crossref","unstructured":"Lov\u00e1sz, L.: Submodular functions and convexity. In: Mathematical programming the state of the art, pp. 235\u2013257. Springer, (1983)","DOI":"10.1007\/978-3-642-68874-4_10"},{"issue":"2","key":"1921_CR24","doi-asserted-by":"crossref","first-page":"249","DOI":"10.1137\/S0895480102408559","volume":"17","author":"S Onn","year":"2003","unstructured":"Onn, S.: Convex matroid optimization. SIAM J. Discret. Math. 17(2), 249\u2013253 (2003)","journal-title":"SIAM J. Discret. Math."},{"issue":"2","key":"1921_CR25","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1007\/s10107-007-0189-2","volume":"118","author":"JB Orlin","year":"2009","unstructured":"Orlin, J.B.: A faster strongly polynomial time algorithm for submodular function minimization. Math. Program. 118(2), 237\u2013251 (2009)","journal-title":"Math. Program."},{"key":"1921_CR26","doi-asserted-by":"crossref","unstructured":"Shi, X., Prokopyev, O.A., Zeng, B.: Sequence independent lifting for the set of submodular maximization problem. In: International Conference on Integer Programming and Combinatorial Optimization, pp. 378\u2013390. Springer, (2020)","DOI":"10.1007\/978-3-030-45771-6_29"},{"issue":"6","key":"1921_CR27","doi-asserted-by":"crossref","first-page":"1715","DOI":"10.1137\/100783352","volume":"40","author":"Z Svitkina","year":"2011","unstructured":"Svitkina, Z., Fleischer, L.: Submodular approximation: sampling-based algorithms and lower bounds. SIAM J. Comput. 40(6), 1715\u20131737 (2011)","journal-title":"SIAM J. Comput."},{"key":"1921_CR28","volume-title":"Integer and Combinatorial Optimization","author":"LA Wolsey","year":"1999","unstructured":"Wolsey, L.A., Nemhauser, G.L.: Integer and Combinatorial Optimization, vol. 55. Wiley (1999)"},{"issue":"3","key":"1921_CR29","doi-asserted-by":"crossref","first-page":"563","DOI":"10.1007\/s10589-017-9958-x","volume":"69","author":"H-H Wu","year":"2018","unstructured":"Wu, H.-H., K\u00fc\u00e7\u00fckyavuz, S.: A two-stage stochastic programming approach for influence maximization in social networks. Comput. Optim. Appl. 69(3), 563\u2013595 (2018)","journal-title":"Comput. Optim. Appl."},{"issue":"1","key":"1921_CR30","doi-asserted-by":"crossref","first-page":"690","DOI":"10.1137\/17M1141576","volume":"29","author":"H-H Wu","year":"2019","unstructured":"Wu, H.-H., K\u00fc\u00e7\u00fckyavuz, S.: Probabilistic partial set covering with an oracle for chance constraints. SIAM J. Optim. 29(1), 690\u2013718 (2019)","journal-title":"SIAM J. Optim."},{"issue":"3","key":"1921_CR31","doi-asserted-by":"crossref","first-page":"356","DOI":"10.1016\/j.orl.2020.04.008","volume":"48","author":"H-H Wu","year":"2020","unstructured":"Wu, H.-H., K\u00fc\u00e7\u00fckyavuz, S.: An exact method for constrained maximization of the conditional value-at-risk of a class of stochastic submodular functions. Oper. Res. Lett. 48(3), 356\u2013361 (2020)","journal-title":"Oper. Res. Lett."},{"issue":"1\u20132","key":"1921_CR32","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1007\/s10107-019-01445-5","volume":"186","author":"W Xie","year":"2021","unstructured":"Xie, W.: On distributionally robust chance constrained programs with Wasserstein distance. Math. Program. 186(1\u20132), 115\u2013155 (2021)","journal-title":"Math. Program."},{"issue":"1\u20132","key":"1921_CR33","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1007\/s10107-016-1033-3","volume":"162","author":"J Yu","year":"2017","unstructured":"Yu, J., Ahmed, S.: Maximizing a class of submodular utility functions with constraints. Math. Program. 162(1\u20132), 145\u2013164 (2017)","journal-title":"Math. Program."},{"key":"1921_CR34","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1016\/j.disopt.2015.07.005","volume":"24","author":"J Yu","year":"2017","unstructured":"Yu, J., Ahmed, S.: Polyhedral results for a class of cardinality constrained submodular minimization problems. Discret. Optim. 24, 87\u2013102 (2017)","journal-title":"Discret. Optim."},{"issue":"1","key":"1921_CR35","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1016\/j.orl.2020.10.007","volume":"49","author":"Q Yu","year":"2020","unstructured":"Yu, Q., K\u00fc\u00e7\u00fckyavuz, S.: A polyhedral approach to bisubmodular function minimization. Oper. Res. Lett. 49(1), 5\u201310 (2020)","journal-title":"Oper. Res. Lett."},{"key":"1921_CR36","doi-asserted-by":"crossref","first-page":"100670","DOI":"10.1016\/j.disopt.2021.100670","volume":"42","author":"Q Yu","year":"2021","unstructured":"Yu, Q., K\u00fc\u00e7\u00fckyavuz, S.: An exact cutting plane method for $$k$$-submodular function maximization. Discret. Optim. 42, 100670 (2021)","journal-title":"Discret. Optim."},{"key":"1921_CR37","unstructured":"Yu, Q., K\u00fc\u00e7\u00fckyavuz, S.: On constrained mixed-integer DR-submodular minimization. (2022). arXiv preprint arXiv:2211.07726"},{"issue":"4","key":"1921_CR38","doi-asserted-by":"crossref","first-page":"2922","DOI":"10.1137\/17M1158707","volume":"28","author":"Y Zhang","year":"2018","unstructured":"Zhang, Y., Jiang, R., Shen, S.: Ambiguous chance-constrained binary programs under mean-covariance information. SIAM J. Optim. 28(4), 2922\u20132944 (2018)","journal-title":"SIAM J. Optim."}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-022-01921-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-022-01921-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-022-01921-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,7,25]],"date-time":"2023-07-25T19:11:04Z","timestamp":1690312264000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-022-01921-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,1,9]]},"references-count":38,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2023,9]]}},"alternative-id":["1921"],"URL":"https:\/\/doi.org\/10.1007\/s10107-022-01921-5","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,1,9]]},"assertion":[{"value":"20 April 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 December 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 January 2023","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}