Journal
OPERATIONS RESEARCH LETTERS
Volume 40, Issue 1, Pages 31-35Publisher
ELSEVIER SCIENCE BV
DOI: 10.1016/j.orl.2011.10.003
Keywords
Approximation algorithm; Phylogenetic tree; Balanced minimum evolution problem
Categories
Funding
- Communaute francaise de Belgique
Ask authors/readers for more resources
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. (C) 2012 Gwenael Joret and Samuel Fiorini. Published by Elsevier B.V. All rights reserved.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available
Share Paper
