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...
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
2014-01-01
|
| Series: | The Scientific World Journal |
| Online Access: | http://dx.doi.org/10.1155/2014/353101 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1850168644747657216 |
|---|---|
| author | Gintaras Palubeckis Armantas Ostreika Arūnas Tomkevičius |
| author_facet | Gintaras Palubeckis Armantas Ostreika Arūnas Tomkevičius |
| author_sort | Gintaras Palubeckis |
| collection | DOAJ |
| 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 | Article |
| id | doaj-art-a26fea50c1c8488d9f29cf8acc0fb494 |
| institution | OA Journals |
| issn | 2356-6140 1537-744X |
| language | English |
| publishDate | 2014-01-01 |
| publisher | Wiley |
| record_format | Article |
| series | The Scientific World Journal |
| spelling | doaj-art-a26fea50c1c8488d9f29cf8acc0fb4942025-08-20T02:20:55ZengWileyThe Scientific World Journal2356-61401537-744X2014-01-01201410.1155/2014/353101353101An Iterated Tabu Search Approach for the Clique Partitioning ProblemGintaras Palubeckis0Armantas Ostreika1Arūnas Tomkevičius2Faculty of Informatics, Kaunas University of Technology, Studentu Street 50-408, 51368 Kaunas, LithuaniaFaculty of Informatics, Kaunas University of Technology, Studentu Street 50-408, 51368 Kaunas, LithuaniaFaculty of Informatics, Kaunas University of Technology, Studentu Street 50-408, 51368 Kaunas, LithuaniaGiven 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.http://dx.doi.org/10.1155/2014/353101 |
| spellingShingle | Gintaras Palubeckis Armantas Ostreika Arūnas Tomkevičius An Iterated Tabu Search Approach for the Clique Partitioning Problem The Scientific World Journal |
| 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 |
| url | http://dx.doi.org/10.1155/2014/353101 |
| work_keys_str_mv | AT gintaraspalubeckis aniteratedtabusearchapproachforthecliquepartitioningproblem AT armantasostreika aniteratedtabusearchapproachforthecliquepartitioningproblem AT arunastomkevicius aniteratedtabusearchapproachforthecliquepartitioningproblem AT gintaraspalubeckis iteratedtabusearchapproachforthecliquepartitioningproblem AT armantasostreika iteratedtabusearchapproachforthecliquepartitioningproblem AT arunastomkevicius iteratedtabusearchapproachforthecliquepartitioningproblem |