DocumentCode :
952374
Title :
Nature Reserve Selection Problem: A Tight Approximation Algorithm
Author :
Bordewich, Magnus ; Semple, Charles
Author_Institution :
Dept. of Comput. Sci., Univ. of Durham, Durham
Volume :
5
Issue :
2
fYear :
2008
Firstpage :
275
Lastpage :
280
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 be conserved so that the phylogenetic diversity of the set of species contained within those regions is maximized. Recently, it has been 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 by Moulton et al.
Keywords :
computational complexity; ecology; NP-hard problem; biodiversity conservation; budgetary constraints; nature reserve selection problem; phylogenetic diversity; species diversity; tight polynomial-time approximation algorithm; Combinatorial algorithms; Trees; Algorithms; Biodiversity; Computational Biology; Conservation of Natural Resources; Ecosystem; Mathematics; Models, Genetic; Phylogeny; Variation (Genetics);
fLanguage :
English
Journal_Title :
Computational Biology and Bioinformatics, IEEE/ACM Transactions on
Publisher :
ieee
ISSN :
1545-5963
Type :
jour
DOI :
10.1109/TCBB.2007.70252
Filename :
4359901
Link To Document :
بازگشت