A Note on the Approximability of the Balanced Minimum Evolution Problem
(2025) , 13 pages
Files
CORE_DP_2025-21.pdf
Open Access - Adobe PDF
- 1011.28 KB
Details
- Authors
- Abstract
- The Balanced Minimum Evolution Problem (BMEP) is an APX -hard nonlinear network design problem that has received attention from the bioinformatics and mathematical programming communities over the past two decades. In this work, we show that if all input distances are positive and bounded, this problem admits a polynomial-time approximation algorithm. We also identify some polynomially solvable instances of the BMEP, including additive dissimilarity matrices, and derive tight lower and upper bounds on the optimal solution to the problem.
- Affiliations
Citations
Catanzaro, D., Pesenti, R., & Pisanu, F. (2025). A Note on the Approximability of the Balanced Minimum Evolution Problem (LIDAM Discussion Paper CORE 2025/21). https://hdl.handle.net/2078.5/273379