Geodesic
Improved upper bounds in clique partitioning problem
Journal of the Belarusian State University. Mathematics and Informatics, Tome 3 (2019), pp. 93-104

Voir la notice de l'article provenant de la source Math-Net.Ru

In this work, a problem of partitioning a complete weighted graph into cliques in such a way that sum of edge weights between vertices belonging to the same clique is maximal is considered. This problem is known as a clique partitioning problem. It arises in many applications and is a varian of classical clustering problem. However, since the problem, as well as many other combinatorial optimization problems, is $NP$-hard, finding its exact solution often appears hard. In this work, a new method for constructing upper bounds of partition quality function values is proposed, and it is shown how to use these upper bounds in branch and bound technique for finding an exact solution. Proposed method is based on the usage of triangles constraining maximal possible quality of partition. Novelty of the method lies in possibility of using triangles overlapping by edges, which allows to find much tighter bounds than when using only non-overlapping subgraphs. Apart from constructing initial estimate, a method of its recalculation, when fixing edges on each step of branch and bound method, is described. Test results of proposed algorithm on generated sets of random graphs are provided. It is shown, that version that uses new bounds works several times faster than previously known methods
Keywords: clique partitioning; branch and bound method; exact solution; upper bounds. 
@article{BGUMI_2019_3_a7,
     author = {A. B. Belyi and S. L. Sobolevskii and A. N. Kourbatski and C. Ratti},
     title = {Improved upper bounds in clique partitioning problem},
     journal = {Journal of the Belarusian State University. Mathematics and Informatics},
     pages = {93--104},
     publisher = {mathdoc},
     volume = {3},
     year = {2019},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/BGUMI_2019_3_a7/}
}
TY  - JOUR
AU  - A. B. Belyi
AU  - S. L. Sobolevskii
AU  - A. N. Kourbatski
AU  - C. Ratti
TI  - Improved upper bounds in clique partitioning problem
JO  - Journal of the Belarusian State University. Mathematics and Informatics
PY  - 2019
SP  - 93
EP  - 104
VL  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/BGUMI_2019_3_a7/
LA  - ru
ID  - BGUMI_2019_3_a7
ER  - 
%0 Journal Article
%A A. B. Belyi
%A S. L. Sobolevskii
%A A. N. Kourbatski
%A C. Ratti
%T Improved upper bounds in clique partitioning problem
%J Journal of the Belarusian State University. Mathematics and Informatics
%D 2019
%P 93-104
%V 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/BGUMI_2019_3_a7/
%G ru
%F BGUMI_2019_3_a7
A. B. Belyi; S. L. Sobolevskii; A. N. Kourbatski; C. Ratti. Improved upper bounds in clique partitioning problem. Journal of the Belarusian State University. Mathematics and Informatics, Tome 3 (2019), pp. 93-104. http://geodesic.mathdoc.fr/item/BGUMI_2019_3_a7/