Approximating the balanced minimum evolution problem

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

Authors: Samuel Fiorini, Gwenaël Joret 

Publication date: 6 July 2012

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

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.

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

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

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)

Cites Work

• Polyhedral geometry of phylogenetic rogue taxa
• Cyclic permutations and evolutionary trees
• Title not available (Why is that?)
• The balanced minimum evolution problem

Cited In (14)

• The balanced minimum evolution problem under uncertain data
• 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
• On the balanced minimum evolution polytope
• Expanding the class of global objective functions for dissimilarity-based hierarchical clustering
• On the approximability of the fixed-tree balanced minimum evolution problem
• An information theory perspective on the balanced minimum evolution problem
• The minimum evolution problem: Overview and classification
• Enumerating vertices of the balanced minimum evolution polytope
• UPGMA and the normalized equidistant minimum evolution problem
• A tutorial on the balanced minimum evolution problem
• Compact mixed integer linear programming models to the minimum weighted tree reconstruction problem
• The balanced minimum evolution problem

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)