Please use this identifier to cite or link to this item:
|Title:||Improved variable neighbourhood search heuristic for quartet clustering|
|Authors:||CONSOLI SERGIO; KORST JAN; PAUWS STEFFEN; GELEIJNSE GIJS|
|Citation:||LECTURE NOTES IN COMPUTER SCIENCE vol. 11328 p. 1-12|
|Type:||Articles in periodicals and books|
|Abstract:||Given a set of n data objects and their pairwise dissimilarities, the goal of quartet clustering is to construct an optimal tree from the total number of possible combinations of quartet topologies on n, where optimality means that the sum of the dissimilarities of the embedded (or consistent) quartet topologies is minimal. This corresponds to an NP-hard combinatorial optimization problem, also referred to as minimum quartet tree cost (MQTC) problem. We provide details and formulation of this challenging problem, and propose a basic greedy heuristic that is characterized by a very high speed and some interesting implementation details. The solution approach, though simple, substantially improves the performance of a Reduced Variable Neighborhood Search for the MQTC problem. The latter is one of the most popular heuristic algorithms for tackling the MQTC problem.|
|JRC Directorate:||Joint Research Centre Corporate Activities|
Files in This Item:
There are no files associated with this item.
Items in repository are protected by copyright, with all rights reserved, unless otherwise indicated.