A Note on the Approximability of the Balanced Minimum Evolution Problem

The Balanced Minimum Evolution Problem (BMEP) is a highly nonlinear NP-hard optimization problem in molecular phylogenetics that has attracted significant attention from the bioinformatics and mathematical programming communities. We investigate conditions under which its practical instances become efficiently approximable. We show that when all pairwise distances are positive and bounded, the problem admits a polynomial-time approximation algorithm with a performance guarantee linked to the interval width. We also characterize polynomially solvable instances, and derive tight bounds on the optimal solution.