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`a Ca’ Foscari di Venezia
Francesco Pisanu: Université catholique de Louvain, LIDAM/CORE, Belgium

No 2025021, LIDAM Discussion Papers CORE from Université catholique de Louvain, Center for Operations Research and Econometrics (CORE)

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.

Pages: 13
Date: 2025-11-13
References: Add references at CitEc
Citations:

Downloads: (external link)
https://dial.uclouvain.be/pr/boreal/en/object/bore ... tastream/PDF_01/view (application/pdf)

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:louvco:2025021

Access Statistics for this paper

More papers in LIDAM Discussion Papers 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 ().