Graph clustering with a~constraint on cluster sizes

V. P. Il'ev ; S. D. Il'eva ; A. A. Navrotskaya

Diskretnyj analiz i issledovanie operacij, Tome 23 (2016) no. 3, pp. 5-20.

Résumé

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.

Détail

Keywords: clustering, approximation, graph, approximation algorithm, performance guarantee.

Bibliographie

[1] 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 | Zbl

[2] M. R. Garey, D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, San Francisco, 1979 | MR | MR | Zbl

[3] V. P. Il'ev, S. D. Il'eva, A. A. Navrotskaya, “Approximation algorithms for graph approximation problems”, J. Appl. Ind. Math., 5:4 (2011), 569–581 | DOI | MR | Zbl

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

[5] V. P. Il'ev, A. A. Navrotskaya, “Computational complexity of the problem of approximation by graphs with connected components of bounded size”, Prikl. Diskretn. Mat., 2011, no. 3, 80–84

[6] V. P. Il'ev, A. A. Navrotskaya, “An approximate and exact solution to one variant of the problem of clustering interconnected objects”, Proc. XI Int. Asian School-Seminar “Optimization Problems for Complex Systems” (Cholpon-Ata, Kyrghyzstan, July 27 – Aug. 7, 2015), Inst. Vychisl. Mat. Mat. Geofiz. SO RAN, Novosibirsk, 2015, 278–283

[7] A. A. Lyapunov, “On the structure and evolution of control systems in connection with the theory of classification”, Problems of Cybernetics, 27, Fizmatgiz, Moscow, 1973, 7–18

[8] G. Š. Fridman, “A graph approximation problem”, Control Systems, 8, Izd. Inst. Mat., Novosibirsk, 1971, 73–75

[9] G. Š. Fridman, “Investigation of a classifying problem on graphs”, Methods of Modelling and Data Processing, Nauka, Novosibirsk, 1976, 147–177

[10] Ailon N., Charikar M., Newman A., “Aggregating inconsistent information: Ranking and clustering”, J. ACM, 55:5 (2008), 1–27 | DOI | MR

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

[12] Ben-Dor A., Shamir R., Yakhimi Z., “Clustering gene expression patterns”, J. Comput. Biol., 6:3–4 (1999), 281–297 | DOI

[13] Charikar M., Guruswami V., Wirth A., “Clustering with qualitative information”, J. Comput. Syst. Sci., 71:3 (2005), 360–383 | DOI | MR | Zbl

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

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

[16] Křivánek M., Morávek J., “NP-hard problems in hierarchical-tree clustering”, Acta Inf., 23 (1986), 311–323 | DOI | MR

[17] Schaeffer S. E., “Graph clustering”, Comput. Sci. Rev., 1:1 (2007), 27–64 | DOI | MR | Zbl

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

[19] Tomescu I., “La reduction minimale d'un graphe à une reunion de cliques”, Discrete Math., 10:1–2 (1974), 173–179 (French) | DOI | MR | Zbl

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