Geodesic
$2$-Approximation algorithms for~two~graph~clustering~problems
Diskretnyj analiz i issledovanie operacij, Tome 27 (2020) no. 3, pp. 88-108.

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

We study a version of the graph $2$-clustering problem and the related semi-supervised problem. In these problems, given an undirected graph, we have to find a nearest $2$-cluster graph, i. e. a graph on the same vertex set with exactly two nonempty connected components each of which is a complete graph. The distance between two graphs is the number of noncoinciding edges. The problems under consideration are NP-hard. In 2008, Coleman, Saunderson, and Wirth presented a polynomial time $2$-approximation algorithm for the analogous problem in which the number of clusters does not exceed $2$. Unfortunately, the method of proving the performance guarantee of the Coleman, Saunderson, and Wirth algorithm is inappropriate for the graph $2$-clustering problem in which the number of clusters equals $2$. We propose a polynomial time $2$-approximation algorithm for the $2$-clustering problem on an arbitrary graph. In contrast to the proof by Coleman, Saunderson, and Wirth, our proof of the performance guarantee of this algorithm does not use switchings. Moreover, we propose an analogous $2$-approximation algorithm for the related semi-supervised problem. Bibliogr. 9.
Keywords: graph, clustering, NP-hard problem, approximation algorithm, guaranteed approximation ratio. 
@article{DA_2020_27_3_a4,
     author = {V. P. Il'ev and S. D. Il'eva and A. V. Morshinin},
     title = {$2${-Approximation} algorithms for~two~graph~clustering~problems},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {88--108},
     publisher = {mathdoc},
     volume = {27},
     number = {3},
     year = {2020},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2020_27_3_a4/}
}
TY  - JOUR
AU  - V. P. Il'ev
AU  - S. D. Il'eva
AU  - A. V. Morshinin
TI  - $2$-Approximation algorithms for~two~graph~clustering~problems
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2020
SP  - 88
EP  - 108
VL  - 27
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2020_27_3_a4/
LA  - ru
ID  - DA_2020_27_3_a4
ER  - 
%0 Journal Article
%A V. P. Il'ev
%A S. D. Il'eva
%A A. V. Morshinin
%T $2$-Approximation algorithms for~two~graph~clustering~problems
%J Diskretnyj analiz i issledovanie operacij
%D 2020
%P 88-108
%V 27
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2020_27_3_a4/
%G ru
%F DA_2020_27_3_a4
V. P. Il'ev; S. D. Il'eva; A. V. Morshinin. $2$-Approximation algorithms for~two~graph~clustering~problems. Diskretnyj analiz i issledovanie operacij, Tome 27 (2020) no. 3, pp. 88-108. http://geodesic.mathdoc.fr/item/DA_2020_27_3_a4/

[1] N. Bansal, A. Blum, S. Chawla, “Correlation clustering”, Mach. Learn, 56:1–3 (2004), 89–113 | DOI | MR | Zbl

[2] T. Coleman, J. Saunderson, A. Wirth, “A local-search 2-approximation for 2-correlation-clustering”, Algorithms, ESA 2008, Proc. 16th Annu. Eur. Symp. (Karlsruhe, Germany, Sept. 15–17, 2008), Lect. Notes Comput. Sci., 5193, Springer, Heidelberg, 2008, 308–319 | DOI | MR | Zbl

[3] R. Shamir, R. Sharan, D. Tsur, “Cluster graph modification problems”, Discrete Appl. Math., 144:1-2 (2004), 173–182 | DOI | MR | Zbl

[4] C. T. Zahn, “Approximating symmetric relations by equivalence relations”, J. Soc. Ind. Appl. Math., 12:4 (1964), 840–847 | DOI | MR | Zbl

[5] V. P. Il'ev, G.. Fridman, “On the problem of approximation by graphs with a fixed number of components”, Soviet Math. Dokl., 25:3 (1982), 666–670 | MR | Zbl

[6] A. A. Ageev, V. P. Il'ev, A. V. Kononov, A. S. Talevnin, “Computational complexity of the graph approximation problem”, J. Appl. Ind. Math., 1:1 (2007), 1–8 | DOI | MR

[7] I. Giotis, V. Guruswami, “Correlation clustering with a fixed number of clusters”, Theory Comput., 2:1 (2006), 249–266 | DOI | MR | Zbl

[8] O. Chapelle, B. Sch-lkopf, A. Zein, Semi-supervised learning, MIT Press, Cambridge, MA, 2006

[9] E. Bair, “Semi-supervised clustering methods”, Wiley Interdisciplinary Reviews: Computational Statistics, 5:5 (2013), 349–361 | DOI