Editorial Board
Publishing Ethics
Author Guide
Submission Prepare Your ManuscriptPeer review
Archive
English version:
Journal of Applied and Industrial Mathematics, 2016, 10:3, 341–348
Volume 23, No 3, 2016, P. 5-20
UDC 519.8
V. P. Il’ev, S. D. Il’eva, and A. A. Navrotskaya
Graph clustering with a constraint on cluster sizes
Abstract:
A graph clustering problem (also known as the graph approximation problem) with a constraint on cluster sizes is studied. A new approximation algorithm is presented for this problem and performance guarantee of this algorithm is obtained. It is shown that the problem belongs to class APX for every fixed $p$, where $p$ is the upper bound on the cluster sizes.
Ill. 2, bibliogr. 20.
Keywords: clustering, approximation, graph, approximation algorithm, performance guarantee.
DOI: 10.17377/daio.2016.23.521
Victor P. Il’ev 1,2
Svetlana D. Il’eva 2
Anna A. Navrotskaya 1,2
1. Sobolev Institute of Mathematics,
4 Koptyug Ave., 630090 Novosibirsk, Russia
2. Omsk State University,
55-A Mir Ave., 644077 Omsk, Russia
e-mail: iljev@mail.ru, nawrocki@ya.ru
Received 28 December 2015
Revised 28 March 2016
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 NP-Completeness, 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 shkoly-seminara “Problemy optimizatsii slozhnykh sistem” (Proc. XI Int. Asian School-Seminar “Optimization Problems for Complex Systems”), Cholpon-Ata, 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. Ben-Dor, 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 local-search 2-approximation for 2-correlation-clustering, 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, NP-hard problems in hierarchical-tree 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.
