Approximating the balanced minimum evolution problem

DOI10.1016/J.ORL.2011.10.003zbMATH Open1242.90275OpenAlexW2040026476MaRDI QIDQ433835FDOQ433835

Authors Samuel Fiorini, Gwenaël Joret

Publication date 6 July 2012

Published in Operations Research Letters (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1104.1080

zbMATH Keywords

phylogenetic treeapproximation algorithmbalanced minimum evolution problem

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59)

Abstract: We prove a strong inapproximability result for the Balanced Minimum Evolution Problem. Our proof also implies that the problem remains NP-hard even when restricted to metric instances. Furthermore, we give a MST-based 2-approximation algorithm for the problem for such instances.

Recommendations

• A tutorial on the balanced minimum evolution problem
• On the approximability of the fixed-tree balanced minimum evolution problem
• A branch-price-and-cut algorithm for the minimum evolution problem
• The minimum evolution problem: Overview and classification
• The balanced minimum evolution problem

Cites work

• scientific article; zbMATH DE number 1945176 (Why is no real title available?)
• Cyclic permutations and evolutionary trees
• Polyhedral geometry of phylogenetic rogue taxa
• The balanced minimum evolution problem

Cited in

(14)

• Compact mixed integer linear programming models to the minimum weighted tree reconstruction problem
• On the balanced minimum evolution polytope
• An information theory perspective on the balanced minimum evolution problem
• The balanced minimum evolution problem
• A tutorial on the balanced minimum evolution problem
• The balanced minimum evolution problem under uncertain data
• The minimum evolution problem: Overview and classification
• A massively parallel branch-\&-bound algorithm for the balanced minimum evolution problem
• Facets of the balanced minimal evolution polytope
• A branch-price-and-cut algorithm for the minimum evolution problem
• UPGMA and the normalized equidistant minimum evolution problem
• Expanding the class of global objective functions for dissimilarity-based hierarchical clustering
• On the approximability of the fixed-tree balanced minimum evolution problem
• Enumerating vertices of the balanced minimum evolution polytope

This page was built for publication: Approximating the balanced minimum evolution problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q433835)