{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,12]],"date-time":"2026-05-12T01:34:14Z","timestamp":1778549654913,"version":"3.51.4"},"reference-count":20,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2016,5,10]],"date-time":"2016-05-10T00:00:00Z","timestamp":1462838400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100002341","name":"Suomen Akatemia","doi-asserted-by":"publisher","award":["250444"],"award-info":[{"award-number":["250444"]}],"id":[{"id":"10.13039\/501100002341","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Finnish Natural Heritage Services"},{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["260393"],"award-info":[{"award-number":["260393"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["260393"],"award-info":[{"award-number":["260393"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Optim Lett"],"published-print":{"date-parts":[[2017,4]]},"DOI":"10.1007\/s11590-016-1039-z","type":"journal-article","created":{"date-parts":[[2016,5,10]],"date-time":"2016-05-10T10:53:11Z","timestamp":1462877591000},"page":"655-665","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":16,"title":["New performance guarantees for the greedy maximization of submodular set functions"],"prefix":"10.1007","volume":"11","author":[{"given":"Jussi","family":"Laitila","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Atte","family":"Moilanen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,5,10]]},"reference":[{"key":"1039_CR1","doi-asserted-by":"crossref","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. Program. 14, 265\u2013294 (1978)","journal-title":"Math. Program."},{"key":"1039_CR2","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1016\/0166-218X(84)90003-9","volume":"7","author":"M Conforti","year":"1984","unstructured":"Conforti, M., Cornu\u00e9jols, G.: Submodular set functions, matroids and the greedy algorithm: tight worst-case bounds and some generalizations of the Rado\u2013Edmonds theorem. Discr. Appl. Math. 7, 251\u2013274 (1984)","journal-title":"Discr. Appl. Math."},{"key":"1039_CR3","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1007\/BF01584082","volume":"1","author":"J Edmonds","year":"1971","unstructured":"Edmonds, J.: Matroids and the greedy algorithm. Math. Program. 1, 127\u2013136 (1971)","journal-title":"Math. Program."},{"key":"1039_CR4","doi-asserted-by":"crossref","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. Manag. Sci. 23, 789\u2013810 (1977)","journal-title":"Manag. Sci."},{"key":"1039_CR5","doi-asserted-by":"crossref","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":"1039_CR6","unstructured":"Goundan, P.R., Schulz, A.S.: Revisiting the greedy approach to submodular set function maximization. Working Paper, Massachusetts Institute of Technology (2007). http:\/\/www.optimization-online.org\/DB_HTML\/2007\/08\/1740.html"},{"key":"1039_CR7","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1017\/CBO9781139177801.004","volume-title":"Tractability: Practical Approaches to Hard Problems","author":"A Krause","year":"2014","unstructured":"Krause, A., Golovin, D.: Submodular function maximization. In: Bordeaux, L., Hamadi, Y., Kohli, P. (eds.) Tractability: Practical Approaches to Hard Problems, pp. 71\u2013104. Cambridge University Press, Cambridge (2014)"},{"key":"1039_CR8","doi-asserted-by":"crossref","DOI":"10.1515\/9781400822539","volume-title":"Supermodularity and Complementarity","author":"DM Topkis","year":"1998","unstructured":"Topkis, D.M.: Supermodularity and Complementarity. Princeton University Press, Princeton (1998)"},{"key":"1039_CR9","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1007\/s00285-011-0405-9","volume":"64","author":"M Bordewich","year":"2012","unstructured":"Bordewich, M., Semple, C.: Budgeted nature reserve selection with diversity feature loss and arbitrary split systems. J. Math. Biol. 64, 69\u201385 (2012)","journal-title":"J. Math. Biol."},{"key":"1039_CR10","doi-asserted-by":"crossref","unstructured":"Golovin, D., Krause, A., Gardner, B., Converse, S.J., Morey, S.: Dynamic resource allocation in conservation planning. In: Proceeding of the 25th AAAI Conference on Artificial Intelligence, pp. 1331\u20131336 (2011)","DOI":"10.1609\/aaai.v25i1.7795"},{"key":"1039_CR11","doi-asserted-by":"crossref","first-page":"571","DOI":"10.1016\/j.biocon.2006.09.008","volume":"134","author":"A Moilanen","year":"2007","unstructured":"Moilanen, A.: Landscape Zonation, benefit functions and target-based planning: unifying reserve selection strategies. Biol. Conserv. 134, 571\u2013579 (2007)","journal-title":"Biol. Conserv."},{"key":"1039_CR12","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1007\/BFb0121195","volume":"8","author":"ML Fisher","year":"1978","unstructured":"Fisher, M.L., Nemhauser, G.L., Wolsey, L.A.: An analysis of approximations for maximizing submodular set functions II. Math. Program. Study 8, 73\u201387 (1978)","journal-title":"Math. Program. Study"},{"key":"1039_CR13","doi-asserted-by":"crossref","first-page":"729","DOI":"10.1287\/moor.2013.0592","volume":"38","author":"A Kulik","year":"2013","unstructured":"Kulik, A., Shachnai, H., Tamir, T.: Approximations for monotone and non-monotone submodular maximization with knapsack constraints. Math. Oper. Res. 38, 729\u2013739 (2013)","journal-title":"Math. Oper. Res."},{"key":"1039_CR14","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1016\/S0167-6377(03)00062-2","volume":"32","author":"M Sviridenko","year":"2004","unstructured":"Sviridenko, M.: A note on maximizing a submodular set function subject to a knapsack constraint. Oper. Res. Lett. 32, 41\u201343 (2004)","journal-title":"Oper. Res. Lett."},{"key":"1039_CR15","doi-asserted-by":"crossref","first-page":"1740","DOI":"10.1137\/080733991","volume":"40","author":"G Calinescu","year":"2011","unstructured":"Calinescu, G., Chekuri, C., P\u00e1l, M., Vondr\u00e1k, J.: Maximizing a submodular set function subject to a matroid constraint. SIAM J. Comput. 40, 1740\u20131766 (2011)","journal-title":"SIAM J. Comput."},{"key":"1039_CR16","first-page":"253","volume":"B23","author":"J Vondr\u00e1k","year":"2010","unstructured":"Vondr\u00e1k, J.: Submodularity and curvature: the optimal algorithm. RIMS K\u00f4ky\u00fbroku Bessatsu B23, 253\u2013266 (2010)","journal-title":"RIMS K\u00f4ky\u00fbroku Bessatsu"},{"key":"1039_CR17","doi-asserted-by":"crossref","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":"1039_CR18","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1007\/s10878-014-9707-3","volume":"31","author":"Z Wang","year":"2016","unstructured":"Wang, Z., Moran, B., Wang, X., Pan, Q.: Approximation for maximizing monotone non-decreasing set functions with a greedy method. J. Comb. Optim. 31, 29\u201343 (2016)","journal-title":"J. Comb. Optim."},{"key":"1039_CR19","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1016\/S0166-218X(00)00366-8","volume":"114","author":"V Il\u2019ev","year":"2001","unstructured":"Il\u2019ev, V.: An approximation guarantee of the greedy descent algorithm for minimizing a supermodular set function. Discr. Appl. Math. 114, 131\u2013146 (2001)","journal-title":"Discr. Appl. Math."},{"key":"1039_CR20","doi-asserted-by":"crossref","first-page":"648","DOI":"10.1016\/j.ejor.2004.09.026","volume":"171","author":"V Il\u2019ev","year":"2006","unstructured":"Il\u2019ev, V., Linker, N.: Performance guarantees of a greedy algorithm for minimizing a supermodular set function on comatroid. Eur. J. Oper. Res. 171, 648\u2013660 (2006)","journal-title":"Eur. J. Oper. Res."}],"container-title":["Optimization Letters"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11590-016-1039-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s11590-016-1039-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11590-016-1039-z","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11590-016-1039-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,8,18]],"date-time":"2023-08-18T04:44:53Z","timestamp":1692333893000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s11590-016-1039-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,5,10]]},"references-count":20,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2017,4]]}},"alternative-id":["1039"],"URL":"https:\/\/doi.org\/10.1007\/s11590-016-1039-z","relation":{},"ISSN":["1862-4472","1862-4480"],"issn-type":[{"value":"1862-4472","type":"print"},{"value":"1862-4480","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,5,10]]}}}