Editorial Board
Publishing Ethics
Author Guide
Submission Prepare Your ManuscriptPeer review
Archive
English version:
Journal of Applied and Industrial Mathematics, 2020, 14:3, 490-502
Volume 27, No 3, 2020, P. 88-108
UDC 519.8
V. P. Il’ev, S. D. Il’eva, and A. V. Morshinin
2-Approximation algorithms for two graph clustering problems
Abstract:
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.
DOI: 10.33048/daio.2020.27.680
Viktor P. Il’ev 1,2
Svetlana D. Il’eva 1
Aleksandr V. Morshinin 2
1. Dostoevsky Omsk State University,
55a Mira Avenue, 644077 Omsk, Russia
2. Omsk Branch of Sobolev Institute of Mathematics,
13 Pevtsov Street, 644043 Omsk, Russia
e-mail: iljev@mail.ru, morshinin.alexander@gmail.com
Received January 10, 2020
Revised May 6, 2020
Accepted May 25, 2020
References
[1] N. Bansal, A. Blum, and S. Chawla, Correlation clustering, Mach. Learn. 56 (1–3), 89–113 (2004).[2] T. Coleman, J. Saunderson, and A. Wirth, A local-search 2-approximation for 2-correlation-clustering, in Algorithms – ESA 2008 (Proc. 16th Annu. Eur. Symp., Karlsruhe, Germany, Sept. 15–17, 2008) (Springer, Heidelberg, 2008), pp. 308–319 (Lect. Notes Comput. Sci., Vol. 5193).
[3] R. Shamir, R. Sharan, and D. Tsur, Cluster graph modification problems, Discrete Appl. Math. 144 (1–2), 173–182 (2004).
[4] C. T. Zahn, Approximating symmetric relations by equivalence relations, J. Soc. Ind. Appl. Math. 12 (4), 840–847 (1964).
[5] V. P. Il’ev and G. Š. Fridman, On the problem of approximation by graphs with a fixed number of components, Dokl. AN SSSR 264 (3), 533–538 (1982) [Russian] [Soviet Math. Dokl. 25 (3), 666–670 (1982)].
[6] A. A. Ageev, V. P. Il’ev, A. V. Kononov, and A. S. Talevnin, Computational complexity of the graph approximation problem, Diskretn. Anal. Issled. Oper., Ser. 1, 13 (1), 3–11 (2006) [Russian] [J. Appl. Ind. Math. 1 (1), 1–8 (2007)].
[7] I. Giotis and V. Guruswami, Correlation clustering with a fixed number of clusters, Theory Comput. 2 (1), 249–266 (2006).
[8] O. Chapelle, B. Schölkopf, and A. Zein, Semi-Supervised Learning (MIT Press, Cambridge, MA, 2006).
[9] E. Bair, Semi-supervised clustering methods, Wiley Interdiscip. Rev., Comput. Stat. 5 (5), 349–361 (2013).
