Nature Reserve Selection Problem: A Tight Approximation Algorithm

Bordewich, M.; Semple, C.

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.

Citation

Bordewich, M., & Semple, C. (2008). Nature Reserve Selection Problem: A Tight Approximation Algorithm. IEEE/ACM Transactions on Computational Biology and Bioinformatics, 5(2), 275-280. https://doi.org/10.1109/tcbb.2007.70252

• Journal Article Type: Article
• Publication Date: Apr 1, 2008
• Deposit Date: Dec 21, 2009
• Publicly Available Date: Jan 6, 2010
• Journal: IEEE/ACM Transactions on Computational Biology and Bioinformatics
• Print ISSN: 1545-5963
• Electronic ISSN: 1557-9964
• Publisher: Association for Computing Machinery (ACM)
• Peer Reviewed: Peer Reviewed
• Volume: 5
• Issue: 2
• Pages: 275-280
• DOI: https://doi.org/10.1109/tcbb.2007.70252
• Public URL: https://durham-repository.worktribe.com/output/1524046
• Publisher URL: http://doi.ieeecomputersociety.org/10.1109/TCBB.2007.70252