A note on the approximability of the balanced minimum evolution problem

Daniele Catanzaro (), Raffaele Pesenti and Francesco Pisanu ()
Additional contact information
Daniele Catanzaro: Université catholique de Louvain, LIDAM/CORE, Belgium
Raffaele Pesenti: Università Ca’ Foscari di Venezia
Francesco Pisanu: Université catholique de Louvain, LIDAM/CORE, Belgium

No 3353, LIDAM Reprints CORE from Université catholique de Louvain, Center for Operations Research and Econometrics (CORE)

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.

Keywords: Balanced minimum evolution problem; Cross-entropy minimization; Unrooted binary trees; Path-length matrices; Approximation algorithms (search for similar items in EconPapers)
Pages: 6
Date: 2026-03-14
Note: In: Operations Research Letters, 2026, vol. 67, 107438
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:cor:louvrp:3353

DOI: 10.1016/j.orl.2026.107438

Access Statistics for this paper

More papers in LIDAM Reprints CORE from Université catholique de Louvain, Center for Operations Research and Econometrics (CORE) Voie du Roman Pays 34, 1348 Louvain-la-Neuve (Belgium). Contact information at EDIRC.
Bibliographic data for series maintained by Alain GILLIS ().