Article ID Journal Published Year Pages File Type
1143133 Operations Research Letters 2012 5 Pages PDF
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
Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Preview
Approximating the balanced minimum evolution problem
Authors
, ,