A Multivariate Complexity Analysis of the Generalized Noah's Ark Problem
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2023
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866915621832228864 |
|---|---|
| author | Komusiewicz, Christian Schestag, Jannik |
| author_facet | Komusiewicz, Christian Schestag, Jannik |
| contents | In the Generalized Noah's Ark Problem, one is given a phylogenetic tree on a set of species X and a set of conservation projects for each species. Each project comes with a cost and raises the survival probability of the corresponding species. The aim is to select a conservation project for each species such that the total cost of the selected projects does not exceed some given threshold and the expected phylogenetic diversity is as large as possible. We study the complexity of Generalized Noah's Ark Problem and some of its special cases with respect to several parameters related to the input structure, such as the number of different costs, the number of different survival probabilities, or the number of species, |X|. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2307_03518 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | A Multivariate Complexity Analysis of the Generalized Noah's Ark Problem Komusiewicz, Christian Schestag, Jannik Data Structures and Algorithms In the Generalized Noah's Ark Problem, one is given a phylogenetic tree on a set of species X and a set of conservation projects for each species. Each project comes with a cost and raises the survival probability of the corresponding species. The aim is to select a conservation project for each species such that the total cost of the selected projects does not exceed some given threshold and the expected phylogenetic diversity is as large as possible. We study the complexity of Generalized Noah's Ark Problem and some of its special cases with respect to several parameters related to the input structure, such as the number of different costs, the number of different survival probabilities, or the number of species, |X|. |
| title | A Multivariate Complexity Analysis of the Generalized Noah's Ark Problem |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2307.03518 |