Professor Magnus Bordewich m.j.r.bordewich@durham.ac.uk
Professor
Budgeted Nature Reserve Selection with diversity feature loss and arbitrary split systems
Bordewich, M.; Semple, C.
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 |
Files
Accepted Journal Article
(309 Kb)
PDF
Copyright Statement
The final publication is available at Springer via http://dx.doi.org/10.1007/s00285-011-0405-9
You might also like
Evaluating Gaussian Grasp Maps for Generative Grasping Models
(2022)
Conference Proceeding
On the Complexity of Optimising Variants of Phylogenetic Diversity on Phylogenetic Networks
(2022)
Journal Article
On the Maximum Agreement Subtree Conjecture for Balanced Trees
(2022)
Journal Article
Autoencoders Without Reconstruction for Textural Anomaly Detection
(2021)
Conference Proceeding
Improving Robotic Grasping on Monocular Images Via Multi-Task Learning and Positional Loss
(2021)
Conference Proceeding
Downloadable Citations
About Durham Research Online (DRO)
Administrator e-mail: dro.admin@durham.ac.uk
This application uses the following open-source libraries:
SheetJS Community Edition
Apache License Version 2.0 (http://www.apache.org/licenses/)
PDF.js
Apache License Version 2.0 (http://www.apache.org/licenses/)
Font Awesome
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2024
Advanced Search