Skip to main content

Research Repository

Advanced Search

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

Bordewich, M.; Semple, C.

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


Authors

C. Semple



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

Files






You might also like



Downloadable Citations