Nature reserve selection problem: a tight approximation algorithm.
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.
Bordewich
Magnus
M
Department of Computer Science, University of Durham, Durham, UK.
Semple
Charles
C
D000465:Algorithms; D044822:Biodiversity; D019295:Computational Biology; D003247:Conservation of Natural Resources; D017753:Ecosystem; D014644:Genetic Variation; D008433:Mathematics; D008957:Models, Genetic; D010802:Phylogeny