Improved variable neighbourhood search heuristic for quartet clustering
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.
CONSOLI Sergio;
KORST Jan;
PAUWS Steffen;
GELEIJNSE Gijs;
2019-10-03
SPRINGER VERLAG
JRC113173
0302-9743 (online),
https://link.springer.com/chapter/10.1007/978-3-030-15843-9_1,
https://publications.jrc.ec.europa.eu/repository/handle/JRC113173,
10.1007/978-3-030-15843-9_1 (online),
Additional supporting files
| File name | Description | File type | |
|---|
