Metaheuristics for the edge-weighted K-cardinality tree problem

摘要: Metaheuristics are successful algorithmic concepts to tackle extit{NP}-hard combinatorial optimization problems. In this paper we deal with metaheuristics for the K-cardinality tree (KCT) problem in edge-weighted graphs. This problem has several applications, which justify need efficient methods obtain good solutions. There are already metaheuristic approaches KCT be found literature. However, there is a lack of benchmark instances and therefore also lack of comparison between these approaches. Moreover, studies comparing -- whatever often suffer from the fact that they compare results obtained on different processors, program code implemented different programming languages based data structures. In contrast studies, aim fair comparison three We carefully chosen set of benchmark characterized by distinguishing features. Our show, due different characteristics areas instance space none our can be identified as best approach. It rather case each approach its advantages certain areas space.