paper

Approximating the Balanced Minimum Evolution Problem

arXiv:1104.1080 · doi:10.1016/j.orl.2011.10.003

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.

Cited by in corpus (1)