Approximating the Balanced Minimum Evolution Problem
classification
💻 cs.DS
cs.DM
keywords
problembalancedevolutioninstancesminimumalgorithmapproximatingapproximation
read the original 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.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.