Related Experiment Videos
Microcanonical optimization algorithm for the Euclidean Steiner problem in Rn with application to phylogenetic
Flávio Montenegro1, José R A Torreão, Nelson Maculan
1COPPE-Programa de Engenharia de Sistemas e Computação, Universidade Federal do Rio de Janeiro, 21941-972 Rio de Janeiro RJ, Brazil.
Physical Review. E, Statistical, Nonlinear, and Soft Matter Physics
|December 20, 2003
Summary
A new microcanonical optimization algorithm efficiently solves the high-dimensional Euclidean Steiner Tree Problem (ESTP). This method finds near-optimal Steiner trees for complex datasets, improving with higher dimensions.
Area of Science:
- Computational geometry
- Optimization algorithms
- High-dimensional data analysis
Background:
- The Euclidean Steiner Tree Problem (ESTP) seeks the shortest network connecting given points, potentially using additional Steiner points.
- Exact solutions for ESTP are computationally infeasible for large, high-dimensional datasets due to combinatorial complexity.
- Existing heuristic methods for high-dimensional ESTP are limited.
Purpose of the Study:
- To introduce a novel microcanonical optimization algorithm for solving the high-dimensional ESTP.
- To demonstrate the algorithm's effectiveness in finding near-optimal Steiner trees.
- To assess the algorithm's performance scaling with dimensionality.
Main Methods:
- Development of a microcanonical optimization algorithm operating on a topology-describing data structure.
- Application of the algorithm to ESTP instances with up to 50 points in 50 dimensions.
- Evaluation of computational time and solution quality.
Main Results:
- The algorithm successfully finds close-to-minimum Steiner trees in reasonable computational time.
- Performance improves as the dimensionality (n) of the problem increases.
- The method is effective for configurations of up to p=50 points in n=50 dimensions.
Conclusions:
- The proposed microcanonical optimization algorithm offers an efficient heuristic for the high-dimensional ESTP.
- Its performance advantage in higher dimensions makes it suitable for complex clustering tasks.
- Applications include phylogenetic inference, demonstrating its utility in real-world high-dimensional problems.