Faller, BeátaSemple, CharlesSteel, M. A.2016-07-282016-07-2820091172-8531http://hdl.handle.net/10092/12533A 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.enAll Rights ReservedDiscussion / Working PapersFields of Research::49 - Mathematical sciences::4901 - Applied mathematics::490102 - Biological mathematics