Approximation scheme for the problem of weighted 2-partitioning with a fixed center of one cluster

A. V. Kel'manov ; A. V. Motkova ; V. V. Shenmaier

Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 23 (2017) no. 3, pp. 159-170

Résumé

We consider the intractable problem of partitioning a finite set of points in Euclidean space into two clusters with minimum sum over the clusters of weighted sums of squared distances between the elements of the clusters and their centers. The center of one cluster is unknown and is defined as the mean value of its elements (i.e., it is the centroid of the cluster). The center of the other cluster is fixed at the origin. The weight factors for the intracluster sums are given as input. We present an approximation algorithm for this problem, which is based on the adaptive grid approach to finding the center of the optimal cluster. We show that the algorithm implements a fully polynomial-time approximation scheme (FPTAS) in the case of fixed space dimension. If the dimension is not fixed but is bounded by a slowly growing function of the number of input points, the algorithm realizes a polynomial-time approximation scheme (PTAS).

Détail

Keywords: Euclidean space, partitioning, NP-hardness, FPTAS, PTAS.

Bibliographie

[1] Kelmanov A. V., Romanchenko S. M., “FPTAS dlya odnoi zadachi poiska podmnozhestva vektorov”, Diskretnyi analiz i issledovanie operatsii, 21:3 (2014), 41–52 | Zbl

[2] Kelmanov A. V., Khandeev V. I., “Polnostyu polinomialnaya approksimatsionnaya skhema dlya spetsialnogo sluchaya odnoi kvadratichnoi evklidovoi zadachi 2-klasterizatsii”, Zhurn. vychisl. matematiki i mat. fiziki, 56:2 (2016), 332–340 | DOI | Zbl

[3] Kel'manov A. V., Motkova A. V., “A fully polynomial-time approximation scheme for a special case of a balanced 2-clustering problem”, Proc. Internat. Conf. on Discrete Optimization and Operations Research (DOOR 2016), Lecture Notes Comp. Sci., 9869, 2016, 182–192 | DOI | MR

[4] A. Aggarwal, H. Imai, N. Katoh, S. Suri, “Finding k points with minimum diameter and related problems”, J. Algorithms, 12:1 (1991), 38–56 | DOI | MR | Zbl

[5] Kelmanov A. V., Pyatkin A. V., “NP-polnota nekotorykh zadach vybora podmnozhestva vektorov”, Diskretnyi analiz i issledovanie operatsii, 17:5 (2010), 37–45 | Zbl

[6] Shenmaier V. V., “Reshenie nekotorykh zadach poiska podmnozhestva vektorov s ispolzovaniem diagramm Voronogo”, Diskretnyi analiz i issledovanie operatsii, 23:4 (2016), 102–115 | DOI | MR | Zbl

[7] Kelmanov A. V, Romanchenko S. M., “Psevdopolinomialnye algoritmy dlya nekotorykh trudnoreshaemykh zadach poiska podmnozhestva vektorov i klasternogo analiza”, Avtomatika i telemekhanika, 2012, no. 2, 156–162 | Zbl

[8] Kelmanov A. V., Romanchenko S. M., “Priblizhennyi algoritm dlya resheniya odnoi zadachi poiska podmnozhestva vektorov”, Diskretnyi analiz i issledovanie operatsii, 18:1 (2011), 61–69 | Zbl

[9] Shenmaier V. V., “Approksimatsionnaya skhema dlya odnoi zadachi poiska podmnozhestva vektorov”, Diskretnyi analiz i issledovanie operatsii, 19:2 (2012), 92–100 | MR | Zbl

[10] E. Kh. Gimadi, A. V. Kelmanov, M. A. Kelmanova, S. A. Khamidullin, “Aposteriornoe obnaruzhenie v chislovoi posledovatelnosti kvaziperiodicheskogo fragmenta pri zadannom chisle povtorov”, Sib. zhurn. industr. matematiki, 9:1(25) (2006), 55–74 | MR | Zbl

[11] E. Kh. Gimadi, A. V. Kel'manov, M. A. Kel'manova, S. A. Khamidullin, “A posteriori detecting a quasiperiodic fragment in a numerical sequence”, Pattern Recognition and Image Analysis, 18:1 (2008), 30–42 | DOI

[12] Kelmanov A. V., Pyatkin A. V., “O slozhnosti nekotorykh zadach poiska podmnozhestv vektorov i klasternogo analiza”, Zhurn. vychisl. matematiki i mat. fiziki, 49:11 (2009), 2059–2065 | MR | Zbl

[13] A. E. Baburin, E. Kh. Gimadi, N. I. Glebov, A. V. Pyatkin, “Zadacha otyskaniya podmnozhestva vektorov s maksimalnym summarnym vesom”, Diskretnyi analiz i issledovanie operatsii, 14:1 (2007), 32–42 | Zbl

[14] Gimadi E. Kh., Pyatkin A. V., Rykov I. A., “O polinomialnoi razreshimosti nekotorykh zadach vybora podmnozhestva vektorov v evklidovom prostranstve fiksirovannoi razmernosti”, Diskretnyi analiz i issledovanie operatsii, 15:6 (2008), 11–19 | Zbl

[15] Gimadi E. Kh., Glazkov Yu. V., Rykov I. A., “O dvukh zadachakh vybora podmnozhestva vektorov s tselochislennymi koordinatami v evklidovom prostranstve s maksimalnoi normoi summy”, Diskretnyi analiz i issledovanie operatsii, 15:4 (2008), 30–43 | Zbl

[16] Kelmanov A. V., Khandeev V. I., “Tochnyi psevdopolinomialnyi algoritm dlya odnoi zadachi dvukhklasternogo razbieniya mnozhestva vektorov”, Diskretnyi analiz i issledovanie operatsii, 22:4 (2015), 50–62 | DOI | Zbl

[17] Dolgushev A. V., Kelmanov A. V., “Priblizhennyi algoritm resheniya odnoi zadachi klasternogo analiza”, Diskretnyi analiz i issledovanie operatsii, 18:2 (2011), 29–40 | MR | Zbl

[18] Dolgushev A. V., Kelmanov A. V., Shenmaier V. V., “Polinomialnaya approksimatsionnaya skhema dlya odnoi zadachi razbieniya konechnogo mnozhestva na dva klastera”, Tr. In-ta matematiki i mekhaniki UrO RAN, 21:3 (2015), 100–109

[19] Kelmanov A. V., Khandeev V. I., “Randomizirovannyi algoritm dlya odnoi zadachi dvukhklasternogo razbieniya mnozhestva vektorov”, Zhurn. vychisl. matematiki i mat. fiziki, 55:2 (2015), 335–344 | DOI | Zbl

[20] Kelmanov A. V., Motkova A. V., “Tochnye psevdopolinomialnye algoritmy dlya zadachi sbalansirovannoi 2-klasterizatsii”, Diskretnyi analiz i issledovanie operatsii, 23:3 (2016), 21–34 | DOI | Zbl

[21] Kelmanov A. V., Pyatkin A. V., “NP-trudnost nekotorykh kvadratichnykh evklidovykh zadach 2-klasterizatsii”, Dokl. RAN, 464:5 (2015), 535–538 | DOI | Zbl

[22] Kelmanov A. V., Pyatkin A. V., “O slozhnosti nekotorykh kvadratichnykh evklidovykh zadach 2-klasterizatsii”, Zhurn. vychisl. matematiki i mat. fiziki, 56:3 (2016), 498–504 | DOI | Zbl

[23] Aggarwal C. C., Data Mining, The Textbook, Springer International Publishing, Cham, 2015, 734 pp. | MR | Zbl

[24] Bishop C. M., Pattern Recognition and Machine Learning, Springer Science+Business Media, LLC, New York, 2006, 738 pp. | MR | Zbl

[25] Hastie T., Tibshirani R., Friedman J., The Elements of statistical learning: Data mining, inference, and prediction, Springer-Verlag, New York, 2009, 763 pp. | DOI | MR | Zbl

[26] G. James, D. Witten, T. Hastie, R. Tibshirani, An introduction to statistical learning, Springer Science+Business Media, LLC, New York, 2013, 426 pp. | DOI | MR | Zbl

[27] Jain A. K., “Data clustering: 50 years beyond k-means”, Pattern Recognition Lett., 31 (2010), 651–666 | DOI

[28] Wirth N., Algorithms + data structures = programs, Prentice Hall, New Jersey, 1976, 366 pp. | MR | Zbl

[29] Ball K., “An elementary introduction to modern convex geometry. Flavors of geometry”, MSRI Publications, 31, ed. ed. S. Levi, 1997, 1–58 | MR | Zbl