title: Microcanonical optimization algorithm for the Euclidean Steiner problem in Rn with application to phylogenetic inference.
abstract: The Euclidean Steiner tree problem in R(n) (ESTP) is that of finding the shortest interconnecting network spanning p given nodes in the Euclidean R(n), with the possible use of extra nodes. Combinatorial explosion precludes the use of exact methods for large high-dimensional ESTP instances, but very few heuristic approaches have so far been proposed for them. Here we introduce a microcanonical optimization algorithm that works over a topology-describing data structure associated to the ESTP solutions, and which is proven able to find close-to-minimum Steiner trees in reasonable computational time, even for configurations of up to p=50 points in n=50 dimensions. Moreover, its performance is shown to increase with n, which makes it especially suited for high-dimensional clustering problems such as those of phylogenetic inference, an instance of which is considered here.
authors.affiliation: COPPE-Programa de Engenharia de Sistemas e Computação, Universidade Federal do Rio de Janeiro, 21941-972 Rio de Janeiro RJ, Brazil.
authors.forename: Flávio
authors.initials: F
authors.lastname: Montenegro
authors.forename: José R A
authors.initials: JR
authors.lastname: Torreão
authors.forename: Nelson
authors.initials: N
authors.lastname: Maculan