Approximating the balanced minimum evolution problem

作     者：Fiorini, Samuel Joret, Gwenael 

作者机构：Univ Libre Bruxelles Dept Math Brussels Belgium Univ Libre Bruxelles Dept Informat Brussels Belgium 

出 版 物：《OPERATIONS RESEARCH LETTERS》 (运筹学快报)

年 卷 期：2012年第40卷第1期

页      面：31-35页

核心收录：

学科分类：1201[管理学-管理科学与工程(可授管理学、工学学位)] 07[理学] 070104[理学-应用数学] 0701[理学-数学] 

基　　金：Communaute francaise de Belgique 

主　　题：Approximation algorithm Phylogenetic tree Balanced minimum evolution problem 

摘      要：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.