Title: Improved variable neighbourhood search heuristic for quartet clustering
Authors: CONSOLI SERGIOKORST JANPAUWS STEFFENGELEIJNSE GIJS
Citation: LECTURE NOTES IN COMPUTER SCIENCE vol. 11328 p. 1-12
Publisher: SPRINGER VERLAG
Publication Year: 2019
JRC N°: JRC113173
ISSN: 0302-9743 (online)
URI: https://link.springer.com/chapter/10.1007/978-3-030-15843-9_1
http://publications.jrc.ec.europa.eu/repository/handle/JRC113173
DOI: 10.1007/978-3-030-15843-9_1
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.