Cargando…

An Iterated Tabu Search Approach for the Clique Partitioning Problem

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 o...

Descripción completa

Detalles Bibliográficos
Autores principales: Palubeckis, Gintaras, Ostreika, Armantas, Tomkevičius, Arūnas
Formato: Online Artículo Texto
Lenguaje:English
Publicado: Hindawi Publishing Corporation 2014
Materias:
Acceso en línea:https://www.ncbi.nlm.nih.gov/pmc/articles/PMC3967401/
https://www.ncbi.nlm.nih.gov/pubmed/24737968
http://dx.doi.org/10.1155/2014/353101
_version_ 1782309023025987584
author Palubeckis, Gintaras
Ostreika, Armantas
Tomkevičius, Arūnas
author_facet Palubeckis, Gintaras
Ostreika, Armantas
Tomkevičius, Arūnas
author_sort Palubeckis, Gintaras
collection PubMed
description 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.
format Online
Article
Text
id pubmed-3967401
institution National Center for Biotechnology Information
language English
publishDate 2014
publisher Hindawi Publishing Corporation
record_format MEDLINE/PubMed
spelling pubmed-39674012014-04-15 An Iterated Tabu Search Approach for the Clique Partitioning Problem Palubeckis, Gintaras Ostreika, Armantas Tomkevičius, Arūnas ScientificWorldJournal Research Article 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. Hindawi Publishing Corporation 2014-03-04 /pmc/articles/PMC3967401/ /pubmed/24737968 http://dx.doi.org/10.1155/2014/353101 Text en Copyright © 2014 Gintaras Palubeckis et al. https://creativecommons.org/licenses/by/3.0/ This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
spellingShingle Research Article
Palubeckis, Gintaras
Ostreika, Armantas
Tomkevičius, Arūnas
An Iterated Tabu Search Approach for the Clique Partitioning Problem
title An Iterated Tabu Search Approach for the Clique Partitioning Problem
title_full An Iterated Tabu Search Approach for the Clique Partitioning Problem
title_fullStr An Iterated Tabu Search Approach for the Clique Partitioning Problem
title_full_unstemmed An Iterated Tabu Search Approach for the Clique Partitioning Problem
title_short An Iterated Tabu Search Approach for the Clique Partitioning Problem
title_sort iterated tabu search approach for the clique partitioning problem
topic Research Article
url https://www.ncbi.nlm.nih.gov/pmc/articles/PMC3967401/
https://www.ncbi.nlm.nih.gov/pubmed/24737968
http://dx.doi.org/10.1155/2014/353101
work_keys_str_mv AT palubeckisgintaras aniteratedtabusearchapproachforthecliquepartitioningproblem
AT ostreikaarmantas aniteratedtabusearchapproachforthecliquepartitioningproblem
AT tomkeviciusarunas aniteratedtabusearchapproachforthecliquepartitioningproblem
AT palubeckisgintaras iteratedtabusearchapproachforthecliquepartitioningproblem
AT ostreikaarmantas iteratedtabusearchapproachforthecliquepartitioningproblem
AT tomkeviciusarunas iteratedtabusearchapproachforthecliquepartitioningproblem