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...
Autores principales: | , , |
---|---|
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 |