An exact algorithm for the minimum quartet tree cost problem

Sergio Consoli (), Jan Korst, Gijs Geleijnse and Steffen Pauws
Additional contact information
Sergio Consoli: Philips Research
Jan Korst: Philips Research
Gijs Geleijnse: Netherlands Comprehensive Cancer Organisation (IKNL)
Steffen Pauws: Philips Research

4OR, 2019, vol. 17, issue 4, No 3, 425 pages

Abstract: Abstract The minimum quartet tree cost (MQTC) problem is a graph combinatorial optimization problem where, given a set of $$n \ge 4$$n≥4 data objects and their pairwise costs (or distances), one wants to construct an optimal tree from the $$3 \cdot {n \atopwithdelims ()4}$$3·n4 quartet topologies on n, where optimality means that the sum of the costs of the embedded (or consistent) quartet topologies is minimal. The MQTC problem is the foundation of the quartet method of hierarchical clustering, a novel hierarchical clustering method for non tree-like (non-phylogeny) data in various domains, or for heterogeneous data across domains. The MQTC problem is NP-complete and some heuristics have been already proposed in the literature. The aim of this paper is to present a first exact solution approach for the MQTC problem. Although the algorithm is able to get exact solutions only for relatively small problem instances, due to the high problem complexity, it can be used as a benchmark for validating the performance of any heuristic proposed for the MQTC problem.

Keywords: Combinatorial optimization; Quartet trees; Minimum quartet tree cost; Exact solution algorithms; Cluster analysis; Graphs; 90C27; 05A05; 05A15; 62H30; 68R10; 05C30; 92E10 (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10288-018-0394-2 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:aqjoor:v:17:y:2019:i:4:d:10.1007_s10288-018-0394-2

Ordering information: This journal article can be ordered from
https://www.springer ... ch/journal/10288/PSE

DOI: 10.1007/s10288-018-0394-2

Access Statistics for this article

4OR is currently edited by Yves Crama, Michel Grabisch and Silvano Martello

More articles in 4OR from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().