Nature reserve selection problem: a tight approximation algorithm

IEEE/ACM Trans Comput Biol Bioinform. 2008 Apr-Jun;5(2):275-80. doi: 10.1109/TCBB.2007.70252.

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.

Publication types

  • Research Support, Non-U.S. Gov't

MeSH terms

  • Algorithms*
  • Biodiversity*
  • Computational Biology
  • Conservation of Natural Resources
  • Ecosystem
  • Genetic Variation
  • Mathematics
  • Models, Genetic
  • Phylogeny