An Iterated Tabu Search Approach for the Clique Partitioning Problem
Joint Authors
Ostreika, Armantas
Tomkevičius, Arūnas
Palubeckis, Gintaras
Source
Issue
Vol. 2014, Issue 2014 (31 Dec. 2014), pp.1-10, 10 p.
Publisher
Hindawi Publishing Corporation
Publication Date
2014-03-04
Country of Publication
Egypt
No. of Pages
10
Main Subjects
Medicine
Information Technology and Computer Science
Abstract EN
Given an edge-weighted undirected graph with weights specifying dissimilarities between pairs of objects, represented by the vertices of the graph, the clique partitioning problem (CPP) is to partition the vertex set of the graph into mutually disjoint subsets such that the sum of the edge weights overall cliques induced by the subsets is as small as possible.
We develop an iterated tabu search (ITS) algorithm for solving this problem.
The proposed algorithm incorporates tabu search, local search, and solution perturbation procedures.
We report computational results on CPP instances of size up to 2000 vertices.
Performance comparisons of ITS against state-of-the-art methods from the literature demonstrate the competitiveness of our approach.
American Psychological Association (APA)
Palubeckis, Gintaras& Ostreika, Armantas& Tomkevičius, Arūnas. 2014. An Iterated Tabu Search Approach for the Clique Partitioning Problem. The Scientific World Journal،Vol. 2014, no. 2014, pp.1-10.
https://search.emarefa.net/detail/BIM-1049299
Modern Language Association (MLA)
Palubeckis, Gintaras…[et al.]. An Iterated Tabu Search Approach for the Clique Partitioning Problem. The Scientific World Journal No. 2014 (2014), pp.1-10.
https://search.emarefa.net/detail/BIM-1049299
American Medical Association (AMA)
Palubeckis, Gintaras& Ostreika, Armantas& Tomkevičius, Arūnas. An Iterated Tabu Search Approach for the Clique Partitioning Problem. The Scientific World Journal. 2014. Vol. 2014, no. 2014, pp.1-10.
https://search.emarefa.net/detail/BIM-1049299
Data Type
Journal Articles
Language
English
Notes
Includes bibliographical references
Record ID
BIM-1049299