title: Nature reserve selection problem: a tight approximation algorithm.
abstract: The Nature Reserve Selection Problem is a problem that arises in the context of studying biodiversity conservation. Subject to budgetary constraints, the problem is to select a set of regions to conserve so that the phylogenetic diversity of the set of species contained within those regions is maximized. Recently, it was shown in a paper by Moulton et al. that this problem is NP-hard. In this paper, we establish a tight polynomial-time approximation algorithm for the Nature Reserve Section Problem. Furthermore, we resolve a question on the computational complexity of a related problem left open in Moulton et al.
authors.affiliation: Department of Computer Science, University of Durham, Durham, UK.
authors.forename: Magnus
authors.initials: M
authors.lastname: Bordewich
authors.forename: Charles
authors.initials: C
authors.lastname: Semple
mesh_terms: D000465:Algorithms; D044822:Biodiversity; D019295:Computational Biology; D003247:Conservation of Natural Resources; D017753:Ecosystem; D014644:Genetic Variation; D008433:Mathematics; D008957:Models, Genetic; D010802:Phylogeny