{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,13]],"date-time":"2026-02-13T14:46:06Z","timestamp":1770993966422,"version":"3.50.1"},"reference-count":20,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2015,9,8]],"date-time":"2015-09-08T00:00:00Z","timestamp":1441670400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["340506"],"award-info":[{"award-number":["340506"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["340506"],"award-info":[{"award-number":["340506"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2017,1]]},"DOI":"10.1007\/s00453-015-0066-y","type":"journal-article","created":{"date-parts":[[2015,9,8]],"date-time":"2015-09-08T14:34:18Z","timestamp":1441722858000},"page":"152-172","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Maximizing a Submodular Function with Viability Constraints"],"prefix":"10.1007","volume":"77","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2269-8193","authenticated-orcid":false,"given":"Wolfgang","family":"Dvo\u0159\u00e1k","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Monika","family":"Henzinger","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"David P.","family":"Williamson","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,9,8]]},"reference":[{"issue":"2","key":"66_CR1","doi-asserted-by":"crossref","first-page":"275","DOI":"10.1109\/TCBB.2007.70252","volume":"5","author":"M Bordewich","year":"2008","unstructured":"Bordewich, M., Semple, C.: Nature reserve selection problem: a tight approximation algorithm. IEEE\/ACM Trans. Comput. Biol. Bioinform. 5(2), 275\u2013280 (2008)","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinform."},{"issue":"1\u20132","key":"66_CR2","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(1\u20132), 69\u201385 (2012)","journal-title":"J. Math. Biol."},{"issue":"1","key":"66_CR3","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1111\/2041-210X.12299","volume":"6","author":"O Chernomor","year":"2015","unstructured":"Chernomor, O., Minh, B.Q., Forest, F., Klaere, S., Ingram, T., Henzinger, M., von Haeseler, A.: Split diversity in constrained conservation prioritization using integer linear programming. Methods Ecol. Evol. 6(1), 83\u201391 (2015)","journal-title":"Methods Ecol. Evol."},{"key":"66_CR4","doi-asserted-by":"crossref","unstructured":"Dvo\u0159\u00e1k, W., Henzinger, M., Williamson, D.P.: Maximizing a Submodular Function with Viability Constraints. In: Bodlaender H.L., Italiano G.F. (eds.), Algorithms\u2014ESA 2013\u2014Proceedings of the 21st Annual European Symposium, Sophia Antipolis, France, September 2\u20134, 2013. Lecture Notes in Computer Science, vol. 8125, pp. 409\u2013420. Springer (2013)","DOI":"10.1007\/978-3-642-40450-4_35"},{"issue":"1","key":"66_CR5","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0006-3207(92)91201-3","volume":"61","author":"DP Faith","year":"1992","unstructured":"Faith, D.P.: Conservation evaluation and phylogenetic diversity. Biol. Conserv. 61(1), 1\u201310 (1992)","journal-title":"Biol. Conserv."},{"key":"66_CR6","doi-asserted-by":"crossref","first-page":"255","DOI":"10.1007\/s00026-011-0093-6","volume":"15","author":"B Faller","year":"2011","unstructured":"Faller, B., Semple, C., Welsh, D.: Optimizing phylogenetic diversity with ecological constraints. Ann. Comb. 15, 255\u2013266 (2011)","journal-title":"Ann. Comb."},{"issue":"4","key":"66_CR7","doi-asserted-by":"crossref","first-page":"634","DOI":"10.1145\/285055.285059","volume":"45","author":"U Feige","year":"1998","unstructured":"Feige, U.: A threshold of ln n for approximating set cover. J. ACM 45(4), 634\u2013652 (1998)","journal-title":"J. ACM"},{"key":"66_CR8","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\u2014II. Math. Program. Study 8, 73\u201387 (1978)","journal-title":"Math. Program. Study"},{"key":"66_CR9","unstructured":"Goundan, P.R., Schulz, A.S.: Revisiting the Greedy Approach to Submodular Set Function Maximization. In: Working Paper, Massachusetts Institute of Technology, 2007. http:\/\/www.optimization-online.org\/DB_HTML\/2007\/08\/1740.html"},{"issue":"1","key":"66_CR10","doi-asserted-by":"crossref","first-page":"101","DOI":"10.1007\/s10878-005-5487-0","volume":"9","author":"T Hsu","year":"2005","unstructured":"Hsu, T., Tsai, K.H., Wang, D.W., Lee, D.T.: Two variations of the minimum Steiner problem. J. Comb. Optim. 9(1), 101\u2013120 (2005)","journal-title":"J. Comb. Optim."},{"issue":"1","key":"66_CR11","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1016\/S0020-0190(99)00031-9","volume":"70","author":"S Khuller","year":"1999","unstructured":"Khuller, S., Moss, A., Naor, J.: The budgeted maximum coverage problem. Inf. Process. Lett. 70(1), 39\u201345 (1999)","journal-title":"Inf. Process. Lett."},{"key":"66_CR12","doi-asserted-by":"crossref","unstructured":"Lee, J., Mirrokni, V.S., Nagarajan, V., Sviridenko, M.: Non-monotone Submodular Maximization Under Matroid and Knapsack Constraints. In: Mitzenmacher M. (ed.) Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC 2009, Bethesda, MD, USA, May 31\u2013June 2 (2009)","DOI":"10.1145\/1536414.1536459"},{"issue":"1","key":"66_CR13","doi-asserted-by":"crossref","first-page":"186","DOI":"10.1016\/j.jtbi.2006.12.021","volume":"246","author":"V Moulton","year":"2007","unstructured":"Moulton, V., Semple, C., Steel, M.: Optimizing phylogenetic diversity under constraints. J. Theor. Biol. 246(1), 186\u2013194 (2007)","journal-title":"J. Theor. Biol."},{"key":"66_CR14","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\u2014I. Math. Program. 14, 265\u2013294 (1978)","journal-title":"Math. Program."},{"issue":"6","key":"66_CR15","doi-asserted-by":"crossref","first-page":"e71","DOI":"10.1371\/journal.pgen.0010071","volume":"1","author":"F Pardi","year":"2005","unstructured":"Pardi, F., Goldman, N.: Species choice for comparative genomics: being greedy works. PLoS Genet. 1(6), e71 (2005)","journal-title":"PLoS Genet."},{"key":"66_CR16","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1007\/BF01202286","volume":"4","author":"E Petrank","year":"1994","unstructured":"Petrank, E.: The hardness of approximation: gap location. Comput. Complex. 4, 133\u2013157 (1994)","journal-title":"Comput. Complex."},{"issue":"4","key":"66_CR17","doi-asserted-by":"crossref","first-page":"527","DOI":"10.1080\/10635150590947023","volume":"54","author":"M Steel","year":"2005","unstructured":"Steel, M.: Phylogenetic diversity and the greedy algorithm. Syst. Biol. 54(4), 527\u2013529 (2005)","journal-title":"Syst. Biol."},{"issue":"2","key":"66_CR18","doi-asserted-by":"crossref","first-page":"218","DOI":"10.1016\/j.ecolecon.2004.12.018","volume":"55","author":"CM Heide van der","year":"2005","unstructured":"van der Heide, C.M., van den Bergh, J., van Ierland, E.: Extending weitzman\u2019s economic ranking of biodiversity protection: combining ecological and genetic considerations. Ecol. Econ. 55(2), 218\u2013223 (2005)","journal-title":"Ecol. Econ."},{"key":"66_CR19","unstructured":"Vondr\u00e1k, J.: Submodular Functions and their Applications. In: SODA 2013 Plenary Talk. http:\/\/theory.stanford.edu\/~jvondrak\/data\/SODA-plenary-talk"},{"key":"66_CR20","doi-asserted-by":"crossref","first-page":"1279","DOI":"10.2307\/2999617","volume":"66","author":"ML Weitzman","year":"1998","unstructured":"Weitzman, M.L.: The Noah\u2019s ark problem. Econometricay 66, 1279\u20131298 (1998)","journal-title":"Econometricay"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-015-0066-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-015-0066-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-015-0066-y","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-015-0066-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,28]],"date-time":"2019-05-28T19:47:22Z","timestamp":1559072842000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-015-0066-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,9,8]]},"references-count":20,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2017,1]]}},"alternative-id":["66"],"URL":"https:\/\/doi.org\/10.1007\/s00453-015-0066-y","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,9,8]]}}}