title: An iterated tabu search approach for the clique partitioning problem.
abstract: 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 over all 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.
authors.affiliation: Faculty of Informatics, Kaunas University of Technology, Studentu Street 50-408, 51368 Kaunas, Lithuania.
authors.forename: Gintaras
authors.identifier: 0000-0002-4991-1505
authors.initials: G
authors.lastname: Palubeckis
authors.affiliation: Faculty of Informatics, Kaunas University of Technology, Studentu Street 50-408, 51368 Kaunas, Lithuania.
authors.forename: Armantas
authors.identifier: 0000-0001-5718-3766
authors.initials: A
authors.lastname: Ostreika
authors.affiliation: Faculty of Informatics, Kaunas University of Technology, Studentu Street 50-408, 51368 Kaunas, Lithuania.
authors.forename: Arūnas
authors.identifier: 0000-0002-8455-6019
authors.initials: A
authors.lastname: Tomkevičius
mesh_terms: D000465:Algorithms; D001185:Artificial Intelligence; D003198:Computer Simulation; D008962:Models, Theoretical; D010363:Pattern Recognition, Automated / Q000379:methods*
references.citation: Phys Rev E Stat Nonlin Soft Matter Phys. 2010 Oct;82(4 Pt 2):046112
references.pmid: 21230350