{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,7]],"date-time":"2025-08-07T20:33:49Z","timestamp":1754598829733,"version":"3.37.3"},"reference-count":29,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2022,6,7]],"date-time":"2022-06-07T00:00:00Z","timestamp":1654560000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2022,6,7]],"date-time":"2022-06-07T00:00:00Z","timestamp":1654560000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CMMI-1826297","CMMI-1826323"],"award-info":[{"award-number":["CMMI-1826297","CMMI-1826323"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Optim Lett"],"published-print":{"date-parts":[[2023,1]]},"DOI":"10.1007\/s11590-022-01890-w","type":"journal-article","created":{"date-parts":[[2022,6,7]],"date-time":"2022-06-07T12:13:19Z","timestamp":1654603999000},"page":"1-26","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["A note on the implications of approximate submodularity in discrete optimization"],"prefix":"10.1007","volume":"17","author":[{"given":"Temitayo","family":"Ajayi","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2222-8201","authenticated-orcid":false,"given":"Taewoo","family":"Lee","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andrew J.","family":"Schaefer","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,6,7]]},"reference":[{"issue":"2","key":"1890_CR1","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. Op. Res. 68(2), 609\u2013630 (2020)","journal-title":"Op. Res."},{"issue":"5","key":"1890_CR2","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 mean-risk minimization in discrete optimization. Oper. Res. Lett. 36(5), 618\u2013622 (2008)","journal-title":"Oper. Res. Lett."},{"issue":"4","key":"1890_CR3","doi-asserted-by":"publisher","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."},{"key":"1890_CR4","doi-asserted-by":"crossref","unstructured":"Atamt\u00fcrk, A., Narayanan, V.: Submodular function minimization and polarity. Math. Program. Ser. B (2021)","DOI":"10.1007\/s10107-020-01607-w"},{"key":"1890_CR5","doi-asserted-by":"publisher","DOI":"10.1561\/9781601987570","volume-title":"Learning with Submodular Functions: A Convex Optimization Perspective","author":"F Bach","year":"2013","unstructured":"Bach, F.: Learning with Submodular Functions: A Convex Optimization Perspective. Now Publishers Inc., Hanover (2013)"},{"key":"1890_CR6","doi-asserted-by":"publisher","first-page":"146","DOI":"10.1007\/BF01580440","volume":"8","author":"E Balas","year":"1975","unstructured":"Balas, E.: Facets of the knapsack polytope. Math. Program. 8, 146\u2013164 (1975)","journal-title":"Math. Program."},{"key":"1890_CR7","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-0348-0478-3","volume-title":"Functional Analysis in Asymmetric Normed Spaces","author":"\u015e Cobza\u015f","year":"2013","unstructured":"Cobza\u015f, \u015e: Functional Analysis in Asymmetric Normed Spaces. Birkh\u00e4user, Basel (2013)"},{"key":"1890_CR8","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/s10107-006-0086-0","volume":"112","author":"G Cornu\u00e9jols","year":"2008","unstructured":"Cornu\u00e9jols, G.: Valid inequalities for mixed integer linear programs. Math. Program. 112, 3\u201344 (2008)","journal-title":"Math. Program."},{"issue":"8","key":"1890_CR9","doi-asserted-by":"publisher","first-page":"789","DOI":"10.1287\/mnsc.23.8.789","volume":"23","author":"G Cornu\u00e9jols","year":"1977","unstructured":"Cornu\u00e9jols, G., Fisher, M.L., Nemhauser, G.L.: Location of bank accounts to optimize float: an analytic study of exact and approximate algorithms. Manage. Sci. 23(8), 789\u2013810 (1977)","journal-title":"Manage. Sci."},{"key":"1890_CR10","first-page":"119","volume-title":"Discrete Location Theory","author":"G Cornu\u00e9jols","year":"1983","unstructured":"Cornu\u00e9jols, G., Nemhauser, G., Wolsey, L.: The uncapacitated facility location problem. In: Mirchandani, P.E., Francis, R.L. (eds.) Discrete Location Theory, pp. 119\u2013171. John Wiley and Sons Inc., New York (1983)"},{"key":"1890_CR11","unstructured":"Das, A., Kempe, D.: Submodular meets spectral: Greedy algorithms for subset selection, sparse approximation and dictionary selection. In: Proceedings of the 28th International Conference on International Conference on Machine Learning, ICML\u201911, pages 1057\u20131064, USA, 2011. Omnipress"},{"key":"1890_CR12","unstructured":"Edmonds, J.: Submodular functions, matroids, and certain polyhedra. In: Combinatorial Structures and Their Applications (Proceedings of Calgary International Conference on Combinatorial Structures and Their Applications), pages 69\u201387, New York, NY, USA, 1970. Gordon and Breach"},{"key":"1890_CR13","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1007\/s10107-020-01508-y","volume":"188","author":"A G\u00f3mez","year":"2021","unstructured":"G\u00f3mez, A.: Strong formulations for conic quadratic optimization with indicator variables. Math. Program. 188, 193\u2013226 (2021)","journal-title":"Math. Program."},{"key":"1890_CR14","unstructured":"Gurobi Optimization LLC. Gurobi optimizer reference manual, 2020"},{"key":"1890_CR15","unstructured":"Halabi, Marwa\u00a0El, Jegelka, Stefanie: Optimal approximation for unconstrained non-submodular minimization. In Hal\u00a0Daum\u00e9 III and Aarti Singh, editors, Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 3961\u20133972. PMLR, 13\u201318 Jul 2020"},{"key":"1890_CR16","doi-asserted-by":"publisher","first-page":"179","DOI":"10.1007\/BF01580442","volume":"8","author":"PL Hammer","year":"1975","unstructured":"Hammer, P.L., Johnson, E.L., Peled, U.N.: Facet of regular 0\u20131 polytopes. Math. Program. 8, 179\u2013206 (1975)","journal-title":"Math. Program."},{"key":"1890_CR17","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-56468-0","volume-title":"Fundamentals of Convex Analysis","author":"J-B Hiriart-Urruty","year":"2001","unstructured":"Hiriart-Urruty, J.-B., Lemar\u00e9chal, C.: Fundamentals of Convex Analysis. Springer-Verlag, Berlin, Heidelberg (2001)"},{"key":"1890_CR18","unstructured":"Horel, T., Singer, Y.: Maximization of approximately submodular functions. In D.\u00a0D. Lee, M.\u00a0Sugiyama, U.\u00a0V. Luxburg, I.\u00a0Guyon, and R.\u00a0Garnett, editors, Advances in Neural Information Processing Systems 29, pages 3045\u20133053. Curran Associates, Inc., 2016"},{"key":"1890_CR19","unstructured":"Iyer, R., Bilmes, J.: Polyhedral aspects of submodularity, convexity and concavity, 2015. arXiv 1506.07329"},{"key":"1890_CR20","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","volume-title":"Complexity of Computer Computations","author":"RM Karp","year":"1972","unstructured":"Karp, R.M.: Reducibility among combinatorial problems. In: Miller, R.E., Thatcher, J.W., Bohlinger, J.D. (eds.) Complexity of Computer Computations, pp. 85\u2013103. Springer, Berlin (1972)"},{"key":"1890_CR21","unstructured":"Krause, A., Cevher, V.: Submodular dictionary selection for sparse representation. In: Proceedings of the 27th International Conference on Machine Learning (ICML-10). Omnipress, 2010"},{"key":"1890_CR22","doi-asserted-by":"crossref","unstructured":"Krause, A., Golovin, D.: Submodular Function Maximization, pages 71\u2013104. Cambridge University Press, 2014","DOI":"10.1017\/CBO9781139177801.004"},{"key":"1890_CR23","doi-asserted-by":"crossref","unstructured":"Lov\u00e1sz, L.: Submodular functions and convexity. In: Mathematical Programming: The State of the Art, pages 235\u2013257. Springer, (1983)","DOI":"10.1007\/978-3-642-68874-4_10"},{"key":"1890_CR24","unstructured":"Mirchandani, P.\u00a0B., Francis, R.\u00a0L.: editors. Discrete Location Theory. Wiley-Interscience Series in Discrete Mathematics and Optimization. Wiley, 1st edition, (1990)"},{"key":"1890_CR25","doi-asserted-by":"publisher","first-page":"313","DOI":"10.1007\/BF02680565","volume":"83","author":"K Murota","year":"1998","unstructured":"Murota, K.: Discrete convex analysis. Math. Program. 83, 313\u2013371 (1998)","journal-title":"Math. Program."},{"key":"1890_CR26","doi-asserted-by":"crossref","unstructured":"Narayanan, H.: Submodular Functions and Electrical Networks, volume\u00a054 of Annals of Discrete Mathematics. North Holland, (1997)","DOI":"10.1016\/S0167-5060(08)70678-2"},{"key":"1890_CR27","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-Interscience, Wiley (1988)"},{"key":"1890_CR28","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00453-012-9719-2","volume":"69","author":"C Seshadri","year":"2014","unstructured":"Seshadri, C., Vondr\u00e1k, J.: Is submodularity testable. Algorithmica 69, 1\u201325 (2014)","journal-title":"Algorithmica"},{"key":"1890_CR29","unstructured":"Zhou, Y., Spanos, C.\u00a0J.: Causal meets submodular: Subset selection with directed information. In D.\u00a0D. Lee, M.\u00a0Sugiyama, U.\u00a0V. Luxburg, I.\u00a0Guyon, and R.\u00a0Garnett, editors, Advances in Neural Information Processing Systems 29, pages 2649\u20132657. Curran Associates, Inc., 2016"}],"container-title":["Optimization Letters"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11590-022-01890-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11590-022-01890-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11590-022-01890-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,4]],"date-time":"2023-01-04T10:58:02Z","timestamp":1672829882000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11590-022-01890-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,6,7]]},"references-count":29,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2023,1]]}},"alternative-id":["1890"],"URL":"https:\/\/doi.org\/10.1007\/s11590-022-01890-w","relation":{},"ISSN":["1862-4472","1862-4480"],"issn-type":[{"type":"print","value":"1862-4472"},{"type":"electronic","value":"1862-4480"}],"subject":[],"published":{"date-parts":[[2022,6,7]]},"assertion":[{"value":"25 March 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 April 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 June 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}