Budgeted Nature Reserve Selection with diversity feature loss and arbitrary split systems

Bordewich, M.; Semple, C.

Abstract

Arising in the context of biodiversity conservation, the Budgeted Nature Reserve Selection (BNRS) problem is to select, subject to budgetary constraints, a set of regions to conserve so that the phylogenetic diversity (PD) of the set of species contained within those regions is maximized. Here PD is measured across either a single rooted tree or a single unrooted tree. Nevertheless, in both settings, this problem is NP-hard. However, it was recently shown that, for each setting, there is a polynomial-time (1−1e)(1−1e) -approximation algorithm for it and that this algorithm is tight. In the first part of the paper, we consider two extensions of BNRS. In the rooted setting we additionally allow for the disappearance of features, for varying survival probabilities across species, and for PD to be measured across multiple trees. In the unrooted setting, we extend to arbitrary split systems. We show that, despite these additional allowances, there remains a polynomial-time (1−1e)(1−1e) -approximation algorithm for each extension. In the second part of the paper, we resolve a complexity problem on computing PD across an arbitrary split system left open by Spillner et al.

Citation

Bordewich, M., & Semple, C. (2012). Budgeted Nature Reserve Selection with diversity feature loss and arbitrary split systems. Journal of Mathematical Biology, 64(1), 69-85. https://doi.org/10.1007/s00285-011-0405-9

• Journal Article Type: Article
• Publication Date: Jan 1, 2012
• Deposit Date: Apr 30, 2012
• Publicly Available Date: Apr 20, 2016
• Journal: Journal of Mathematical Biology
• Print ISSN: 0303-6812
• Electronic ISSN: 1432-1416
• Publisher: Springer
• Peer Reviewed: Peer Reviewed
• Volume: 64
• Issue: 1
• Pages: 69-85
• DOI: https://doi.org/10.1007/s00285-011-0405-9
• Public URL: https://durham-repository.worktribe.com/output/1506746