On approximation of optimizing phylogenetic diversity for cluster systems

Simple item page
dc.contributor.authorFaller, Beáta
dc.contributor.authorSemple, Charles
dc.contributor.authorSteel, M. A.
dc.date.accessioned2016-07-28T21:42:44Z
dc.date.available2016-07-28T21:42:44Z
dc.date.issued2009en
dc.description.abstractA basic question in conservation biology is how to maximize future biodiversity as species face extinction. One way to approach this question is by measuring the diversity of a set of species in terms of the evolutionary history that those species span in a phylogenetic tree. Maximizing the resulting 'phylogenetic diversity' (PD) is one prominent selection criteria for deciding which species to conserve. The basic PD optimization problem aims to find a k-element subset of a given species set that has maximum PD among all such subsets. In this paper, we consider a generalization of this problem, which arises in situations where we do not know the true tree, or where evolution is not tree-like. We show that a greedy algorithm gives a (1-e⁻¹)-approximation to the general PD optimization problem, and that there is no polynomial-time algorithm that achieves a better approximation ratio unless P=NP.en
dc.identifier.issn1172-8531
dc.identifier.urihttp://hdl.handle.net/10092/12533
dc.language.isoen
dc.publisherUniversity of Canterburyen
dc.rightsAll Rights Reserveden
dc.rights.urihttps://canterbury.libguides.com/rights/theses
dc.subject.anzsrcFields of Research::49 - Mathematical sciences::4901 - Applied mathematics::490102 - Biological mathematicsen
dc.titleOn approximation of optimizing phylogenetic diversity for cluster systemsen
dc.typeDiscussion / Working Papers
uc.collegeFaculty of Engineering
uc.departmentSchool of Engineeringen
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
fallar_semple_steel_ucdms2009-1_report.pdf
Size:
780.59 KB
Format:
Adobe Portable Document Format
Description:
Download
License bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
license.txt
Size:
1.71 KB
Format:
Item-specific license agreed upon to submission
Description:
Download
Collections
Engineering: Reports