BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Leaf Selection for Maximising Diversity in a Tree - Fabio Pardi
DTSTART:20061016T130000Z
DTEND:20061016T140000Z
UID:TALK5207@talks.cam.ac.uk
CONTACT:David MacKay
DESCRIPTION:I consider a family of optimisation problems with the followin
 g form: given a tree T whose edges have an associated "length"\, select (s
 ubject to various constraints) a subset S of leaves from T\, so that the t
 otal length of the (Steiner) subtree that connects them (called "diversity
 " of S) is maximised.  According to the nature of the constraints\, the pr
 oblem has varying computational complexity (reaching NP-hardness) and diff
 erent algorithmic solutions are devisable\, namely a greedy and a pseudo-p
 olynomial dynamic programming algorithm.\n\nI will discuss the relevance o
 f this problem in biology\, where some attention has recently been given t
 o the selection of maximally diverse sets of genes\, populations or specie
 s in the evolutionary tree relating them.\n\nAs the leaves don't need to b
 e biological entities and the tree does not need to reflect evolutionary r
 elationships\, I will be particularly curious to hear from the public abou
 t any possible applications in their fields of interest.
LOCATION:Ryle Seminar Room\, Cavendish Laboratory
END:VEVENT
END:VCALENDAR