A note on the approximability of the balanced minimum evolution problem

Catanzaro, Daniele;Pesenti, Raffaele;Pisanu, Francesco
(2026) Operations Research Letters — Vol. 67, p. 107438 (2026)

Files

CORE_RP_3353.pdf
  • Open Access
  • Adobe PDF
  • 776.61 KB
Download

Details

Authors
Abstract
The Balanced Minimum Evolution Problem (BMEP) is a highly nonlinear -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.
Affiliations

Citations

  • APA
  • Chicago
  • FWB

Catanzaro, D., Pesenti, R., & Pisanu, F. (2026). A note on the approximability of the balanced minimum evolution problem. Operations Research Letters, 67, 107438. https://doi.org/10.1016/j.orl.2026.107438 (Original work published 2026)