{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,28]],"date-time":"2025-08-28T12:03:25Z","timestamp":1756382605955,"version":"3.37.3"},"reference-count":31,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2021,1,28]],"date-time":"2021-01-28T00:00:00Z","timestamp":1611792000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,1,28]],"date-time":"2021-01-28T00:00:00Z","timestamp":1611792000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/100000001","name":"US National Science Foundation","doi-asserted-by":"crossref","award":["1807260"],"award-info":[{"award-number":["1807260"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/100006133","name":"Advanced Research Projects Agency - Energy","doi-asserted-by":"publisher","award":["260801540061"],"award-info":[{"award-number":["260801540061"]}],"id":[{"id":"10.13039\/100006133","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2022,11]]},"DOI":"10.1007\/s10107-020-01607-w","type":"journal-article","created":{"date-parts":[[2021,1,28]],"date-time":"2021-01-28T16:08:34Z","timestamp":1611850114000},"page":"57-67","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":12,"title":["Submodular function minimization and polarity"],"prefix":"10.1007","volume":"196","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-1220-808X","authenticated-orcid":false,"given":"Alper","family":"Atamt\u00fcrk","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Vishnu","family":"Narayanan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,1,28]]},"reference":[{"key":"1607_CR1","doi-asserted-by":"publisher","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. Progr. 128, 149\u2013169 (2011)","journal-title":"Math. Progr."},{"key":"1607_CR2","doi-asserted-by":"publisher","first-page":"433","DOI":"10.1287\/opre.2016.1570","volume":"65","author":"A Atamt\u00fcrk","year":"2017","unstructured":"Atamt\u00fcrk, A., G\u00f3mez, A.: Maximizing a class of utility functions over the vertices of a polytope. Oper. Res. 65, 433\u2013445 (2017)","journal-title":"Oper. Res."},{"key":"1607_CR3","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1007\/s10107-018-1301-5","volume":"170","author":"A Atamt\u00fcrk","year":"2018","unstructured":"Atamt\u00fcrk, A., G\u00f3mez, A.: Strong formulations for quadratic optimization with M-matrices and indicator variables. Math. Progr. 170, 141\u2013176 (2018)","journal-title":"Math. Progr."},{"key":"1607_CR4","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, 609\u2013630 (2020)","journal-title":"Oper. Res."},{"key":"1607_CR5","doi-asserted-by":"publisher","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. Glob. Optim. 73, 677\u2013699 (2019)","journal-title":"J. Glob. Optim."},{"key":"1607_CR6","doi-asserted-by":"publisher","first-page":"1943","DOI":"10.1137\/15M1033009","volume":"27","author":"A Atamt\u00fcrk","year":"2017","unstructured":"Atamt\u00fcrk, A., K\u00fc\u00e7\u00fckyavuz, S., Tezel, B.: Path cover and path pack inequalities for the capacitated fixed-charge network flow problem. SIAM J. Optim. 27, 1943\u20131976 (2017)","journal-title":"SIAM J. Optim."},{"key":"1607_CR7","doi-asserted-by":"publisher","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 risk minimization in discrete optimization. Oper. Res. Lett. 36, 618\u2013622 (2008)","journal-title":"Oper. Res. Lett."},{"key":"1607_CR8","doi-asserted-by":"publisher","first-page":"4700","DOI":"10.1287\/mnsc.2017.2849","volume":"64","author":"D Bergman","year":"2017","unstructured":"Bergman, D., Cire, A.A.: Discrete nonlinear optimization by state-space decompositions. Manag. Sci. 64, 4700\u20134720 (2017)","journal-title":"Manag. Sci."},{"key":"1607_CR9","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1016\/0166-218X(84)90111-2","volume":"7","author":"MW Carter","year":"1984","unstructured":"Carter, M.W.: The indefinite zero-one quadratic problem. Discret. Appl. Math. 7, 23\u201344 (1984)","journal-title":"Discret. Appl. Math."},{"key":"1607_CR10","first-page":"69","volume-title":"Combinatorial Structures and their Applications","author":"J Edmonds","year":"1971","unstructured":"Edmonds, J.: Submodular functions, matroids and certain polyhedra. In: Guy, R. (ed.) Combinatorial Structures and their Applications, vol. 11, pp. 69\u201387. Gordon and Breach, New York (1971)"},{"key":"1607_CR11","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1016\/S0167-5060(08)70734-9","volume-title":"Studies in Integer Programming, volume 1 of Annals of Discrete Mathematics","author":"J Edmonds","year":"1977","unstructured":"Edmonds, J., Giles, R.: A min-max relation for submodular functions on graphs. In: Hammer, P., Johnson, E., Korte, B., Nemhauser, G. (eds.) Studies in Integer Programming, volume 1 of Annals of Discrete Mathematics, pp. 185\u2013204. Elsevier, New York (1977)"},{"key":"1607_CR12","doi-asserted-by":"publisher","first-page":"1133","DOI":"10.1137\/090779346","volume":"40","author":"U Feige","year":"2011","unstructured":"Feige, U., Mirrokni, V.S., Vondr\u00e1k, J.: Maximizing non-monotone submodular functions. SIAM J. Comput. 40, 1133\u20131153 (2011)","journal-title":"SIAM J. Comput."},{"key":"1607_CR13","volume-title":"Submodular Functions and Optimization, volume 58 of Annals of Discrete Mathematics","author":"S Fujishige","year":"2005","unstructured":"Fujishige, S.: Submodular Functions and Optimization, volume 58 of Annals of Discrete Mathematics, 2nd edn. Elsevier, Amsterdam (2005)","edition":"2"},{"key":"1607_CR14","doi-asserted-by":"publisher","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, 169\u2013197 (1981)","journal-title":"Combinatorica"},{"key":"1607_CR15","unstructured":"Han, S., G\u00f3mez, A., Prokopyev, O.\u00a0A.: Fractional 0-1 programming and submodularity (2020). arXiv:2012.07235"},{"key":"1607_CR16","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1007\/s10107-006-0084-2","volume":"112","author":"S Iwata","year":"2008","unstructured":"Iwata, S.: Submodular function minimization. Math. Progr. 112, 45\u201364 (2008)","journal-title":"Math. Progr."},{"key":"1607_CR17","doi-asserted-by":"publisher","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, 761\u2013777 (2001)","journal-title":"J. ACM"},{"key":"1607_CR18","doi-asserted-by":"publisher","first-page":"2053","DOI":"10.1137\/090750020","volume":"23","author":"J Lee","year":"2010","unstructured":"Lee, J., Mirrokni, V.S., Nagarajan, V., Sviridenko, M.: Maximizing nonmonotone submodular functions under matroid or knapsack constraints. SIAM J. Discret. Math. 23, 2053\u20132078 (2010)","journal-title":"SIAM J. Discret. Math."},{"key":"1607_CR19","doi-asserted-by":"publisher","first-page":"154","DOI":"10.1016\/0377-2217(95)00205-7","volume":"94","author":"H Lee","year":"1996","unstructured":"Lee, H., Nemhauser, G.L., Wang, Y.: Maximizing a submodular function by integer programming: polyhedral results for the quadratic case. Eur. J. Oper. Res. 94, 154\u2013166 (1996)","journal-title":"Eur. J. Oper. Res."},{"key":"1607_CR20","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1007\/978-3-642-68874-4_10","volume-title":"Mathematical Programming-State of the Art","author":"L Lov\u00e1sz","year":"1983","unstructured":"Lov\u00e1sz, L.: Submodular functions and convexity. In: Bachem, A., Gr\u00f6tschel, M., Korte, B. (eds.) Mathematical Programming-State of the Art, pp. 235\u2013257. Springer, Berlin (1983)"},{"key":"1607_CR21","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1287\/moor.3.3.177","volume":"3","author":"GL Nemhauser","year":"1978","unstructured":"Nemhauser, G.L., Wolsey, L.A.: Best algorithms for approximating the maximum of a submodular set function. Math. Oper. Res. 3, 177\u2013188 (1978)","journal-title":"Math. Oper. Res."},{"key":"1607_CR22","first-page":"279","volume-title":"Annals of Discrete Mathematics (11), volume 59 of North-Holland Mathematics Studies","author":"G Nemhauser","year":"1981","unstructured":"Nemhauser, G., Wolsey, L.: Maximizing submodular set functions: formulations and analysis of algorithms. In: Hansen, P. (ed.) Annals of Discrete Mathematics (11), volume 59 of North-Holland Mathematics Studies, pp. 279\u2013301. North-Holland, Amsterdam (1981)"},{"key":"1607_CR23","doi-asserted-by":"publisher","DOI":"10.1002\/9781118627372","volume-title":"Integer and Combinatorial Optimization","author":"GL Nemhauser","year":"1988","unstructured":"Nemhauser, G.L., Wolsey, L.A.: Integer and Combinatorial Optimization. Wiley, New York (1988)"},{"key":"1607_CR24","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1007\/BF01588971","volume":"14","author":"GL Nemhauser","year":"1978","unstructured":"Nemhauser, G.L., Wolsey, L.A., Fisher, M.L.: An analysis of approximations for maximizing submodular set functions-I. Math. Progr. 14, 265\u2013294 (1978)","journal-title":"Math. Progr."},{"key":"1607_CR25","volume-title":"Interior-Point Polynomial Algorithms for Convex Programming","author":"Y Nesterov","year":"1993","unstructured":"Nesterov, Y., Nemirovski, A.: Interior-Point Polynomial Algorithms for Convex Programming. SIAM, Philedelphia (1993)"},{"key":"1607_CR26","doi-asserted-by":"publisher","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. Progr. 118, 237\u2013251 (2009)","journal-title":"Math. Progr."},{"key":"1607_CR27","doi-asserted-by":"publisher","first-page":"346","DOI":"10.1006\/jctb.2000.1989","volume":"80","author":"A Schrijver","year":"2000","unstructured":"Schrijver, A.: A combinatorial algorithm minimizing submodular functions in strongly polynomial time. J. Comb. Theory, Ser. B 80, 346\u2013355 (2000)","journal-title":"J. Comb. Theory, Ser. B"},{"key":"1607_CR28","volume-title":"Combinatorial Optimization: Polyhedra and Efficiency","author":"A Schrijver","year":"2003","unstructured":"Schrijver, A.: Combinatorial Optimization: Polyhedra and Efficiency. Springer, Berlin (2003)"},{"key":"1607_CR29","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1287\/opre.26.2.305","volume":"26","author":"DM Topkis","year":"1978","unstructured":"Topkis, D.M.: Minimizing a submodular function on a lattice. Oper. Res. 26, 305\u2013321 (1978)","journal-title":"Oper. Res."},{"key":"1607_CR30","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1016\/0167-6377(89)90036-9","volume":"8","author":"LA Wolsey","year":"1988","unstructured":"Wolsey, L.A.: Submodularity and valid inequalities in capacitated fixed charge networks. Oper. Res. Lett. 8, 119\u2013124 (1988)","journal-title":"Oper. Res. Lett."},{"key":"1607_CR31","doi-asserted-by":"publisher","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. Progr. 162, 145\u2013164 (2017)","journal-title":"Math. Progr."}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-020-01607-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-020-01607-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-020-01607-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,11,8]],"date-time":"2022-11-08T00:31:06Z","timestamp":1667867466000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-020-01607-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,1,28]]},"references-count":31,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2022,11]]}},"alternative-id":["1607"],"URL":"https:\/\/doi.org\/10.1007\/s10107-020-01607-w","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"type":"print","value":"0025-5610"},{"type":"electronic","value":"1436-4646"}],"subject":[],"published":{"date-parts":[[2021,1,28]]},"assertion":[{"value":"22 January 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 December 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 January 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}