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

Area of Science:

• Conservation Science
• Computational Biology
• Optimization

Background:

• The Budgeted Nature Reserve Selection (BNRS) problem aims to maximize phylogenetic diversity (PD) within budget constraints for biodiversity conservation.
• The problem is NP-hard in both rooted and unrooted tree settings, with existing tight (1 - 1/e)-approximation algorithms.

Purpose of the Study:

• To develop polynomial-time approximation algorithms for extended BNRS problems.
• To address PD computation complexity in arbitrary split systems.

Main Methods:

• Developed new algorithms for extended BNRS, incorporating feature disappearance, varying survival probabilities, and multi-tree PD measurements.
• Extended BNRS to arbitrary split systems in the unrooted setting.
• Resolved a complexity problem concerning PD computation across arbitrary split systems.

Main Results:

• Achieved polynomial-time (1 - 1/e)-approximation algorithms for two extensions of the BNRS problem.
• Demonstrated that the (1 - 1/e) approximation guarantee holds even with added complexities.
• Resolved an open complexity question related to PD computation in arbitrary split systems.

Conclusions:

• Efficient approximation algorithms exist for complex BNRS scenarios, aiding biodiversity conservation.
• The research advances the computational understanding of phylogenetic diversity.
• The findings provide practical tools for optimizing conservation reserve selection under budget limitations.