On the approximability of the fixed-tree balanced minimum evolution problem

Frohn, Martin
(2021) Optimization Letters — Vol. 15, n° 6, p. 2321-2329 (2021)

Files

Frohn_CORE.pdf
  • Open Access
  • Adobe PDF
  • 419.07 KB
Download

Details

Authors
  • Frohn, Martinorcid-logoUCLouvain
    Author
Abstract
The Fixed-Tree BMEP (FT-BMEP) is a special case of the Balanced Minimum Evolution Problem (BMEP) that consists of finding the assignment of a set of n taxa to the n leaves of a given unrooted binary tree so as to minimize the BMEP objective function. Deciding the computational complexity of the FT-BMEP has been an open problem for almost a decade. Here, we show that a few modifications to Fiorini and Joret’s proof of the NP-hardness of the BMEP suffice to prove the general NP-hardness of the FT-BMEP as well as its strong inapproximability.
Affiliations

Citations

  • APA
  • Chicago
  • FWB

Frohn, M. (2021). On the approximability of the fixed-tree balanced minimum evolution problem. Optimization Letters, 15(6), 2321-2329. https://doi.org/10.1007/s11590-020-01677-x (Original work published 2021)