Approximating the balanced minimum evolution problem |
| |
| Authors: | Samuel Fiorini Gwenaël Joret |
| |
| Institution: | a Université Libre de Bruxelles, Département de Mathématique, Belgiumb Université Libre de Bruxelles, Département d’Informatique, Belgium |
| |
| 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. |
| |
| Keywords: | Approximation algorithm Phylogenetic tree Balanced minimum evolution problem |
| 本文献已被 ScienceDirect 等数据库收录！ |
