Professor Magnus Bordewich m.j.r.bordewich@durham.ac.uk
Professor
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.
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 |
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
Evaluating Gaussian Grasp Maps for Generative Grasping Models
(2022)
Presentation / Conference Contribution
Improving Robotic Grasping on Monocular Images Via Multi-Task Learning and Positional Loss
(2021)
Presentation / Conference Contribution
Autoencoders Without Reconstruction for Textural Anomaly Detection
(2021)
Presentation / Conference Contribution
On the approximation complexity hierarchy.
(2011)
Presentation / Conference Contribution
Accuracy Guarantees for Phylogeny Reconstruction Algorithms Based on Balanced Minimum Evolution.
(2010)
Presentation / Conference Contribution
About Durham Research Online (DRO)
Administrator e-mail: dro.admin@durham.ac.uk
This application uses the following open-source libraries:
Apache License Version 2.0 (http://www.apache.org/licenses/)
Apache License Version 2.0 (http://www.apache.org/licenses/)
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