ENRU
English version: Journal of Applied and Industrial Mathematics, 2016, 10:3, 341–348 

Volume 23, No 3, 2016, P. 520 UDC 519.8
Keywords: clustering, approximation, graph, approximation algorithm, performance guarantee. DOI: 10.17377/daio.2016.23.521 Victor P. Il’ev ^{1,2} Received 28 December 2015 References[1] 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, No. 1, 3–11, 2006. Translated in J. Appl. Ind. Math., 1, No. 1, 1–8, 2007.[2] M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NPCompleteness, Freeman, San Francisco, 1979. Translated under the title Vychislitel’nye mashiny i trudnoreshaemye zadachi, Mir, Moscow, 1982. [3] V. P. Il’ev, S. D. Il’eva, and A. A. Navrotskaya, Approximation algorithms for graph approximation problems, Diskretn. Anal. Issled. Oper., 18, No. 1, 41–60, 2011. Translated in J. Appl. Ind. Math., 5, No. 4, 569–581, 2011. [4] V. P. Il’ev and G. S. Fridman, On the problem of approximation by graphs with a fixed number of components, Dokl. Akad. Nauk SSSR, 264, No. 3, 533–538, 1982. Translated in Sov. Math. Dokl., 25, No. 3, 666–670, 1982. [5] V. P. Il’ev and A. A. Navrotskaya, Computational complexity of the problem of approximation by graphs with connected components of bounded size, Prikl. Diskretn. Mat., No. 3, 80–84, 2011. [6] V. P. Il’ev and A. A. Navrotskaya, An approximate and exact solution to one variant of the problem of clustering interconnected objects, in Tr. XI Mezhdunarodnoi aziatskoi shkolyseminara “Problemy optimizatsii slozhnykh sistem” (Proc. XI Int. Asian SchoolSeminar “Optimization Problems for Complex Systems”), CholponAta, Kyrghyzstan, July 27 – Aug. 7, 2015, pp. 278–283, Inst. Vychisl. Mat. Mat. Geofiz. SO RAN, Novosibirsk, 2015. [7] A. A. Lyapunov, On the structure and evolution of control systems in connection with the theory of classification, Problemy kibernetiki (Problems of Cybernetics), Vol. 27, pp. 7–18, Fizmatgiz, Moscow, 1973. [8] G. S. Fridman, A graph approximation problem, in Upravlyaemye sistemy (Control Systems), Vol. 8, pp. 73–75, Izd. Inst. Mat., Novosibirsk, 1971. [9] G. S. Fridman, Investigation of a classifying problem on graphs, in Metody modelirovaniya i obrabotka informatsii (Methods of Modelling and Data Processing), pp. 147–177, Nauka, Novosibirsk, 1976. [10] N. Ailon, M. Charikar, and A. Newman, Aggregating inconsistent information: Ranking and clustering, J. ACM, 55, No. 5, 1–27, 2008. [11] N. Bansal, A. Blum, and S. Chawla, Correlation clustering, Mach. Learn., 56, No. 1–3, 89–113, 2004. [12] A. BenDor, R. Shamir, and Z. Yakhimi, Clustering gene expression patterns, J. Comput. Biol., 6, No. 3–4, 281–297, 1999. [13] M. Charikar, V. Guruswami, and A. Wirth, Clustering with qualitative information, J. Comput. Syst. Sci., 71, No. 3, 360–383, 2005. [14] T. Coleman, J. Saunderson, and A. Wirth, A localsearch 2approximation for 2correlationclustering, in Algorithms  ESA 2008 (Proc. 16th Annual Eur. Symp. Algorithms, Karlsruhe, Germany, Sept. 15–17, 2008), pp. 308–319, Springer, Heidelberg, 2008 (Lect. Notes Comput. Sci., Vol. 5193). [15] I. Giotis and V. Guruswami, Correlation clustering with a fixed number of clusters, Theory Comput., 2, 249–266, 2006. [16] M. Krivánek and J. Morávek, NPhard problems in hierarchicaltree clustering, Acta Inform., 23, 311–323, 1986. [17] S. E. Schaeffer, Graph clustering, Comput. Sci. Rev., 1, No. 1, 27–64, 2007. [18] R. Shamir, R. Sharan, and D. Tsur, Cluster graph modification problems, Discrete Appl. Math., 144, No. 1–2, 173–182, 2004. [19] I. Tomescu, Minimal reduction of a graph to a union of cliques, Discrete Math., 10, No. 1, 173–179, 1974 [French]. [20] C. T. Zahn, Jr., Approximating symmetric relations by equivalence relations, J. Soc. Ind. Appl. Math., 12, No. 4, 840–847, 1964. 

© Sobolev Institute of Mathematics, 2015  