Geodesic
An exact pseudopolynomial algorithm for a~bi-partitioning problem
Diskretnyj analiz i issledovanie operacij, Tome 22 (2015) no. 4, pp. 50-62.

Voir la notice de l'article provenant de la source Math-Net.Ru

We consider the strongly NP-hard problem of partitioning a set of Euclidean vectors into two sets (clusters) under the criterion of minimum sum-of-squared distances from the elements of clusters to their centers. The center of the first cluster is the average value of the vectors in the cluster, and the center of the second one is the origin. We prove that the problem is solvable in polynomial time in the case of fixed space dimension. We also present a pseudopolynomial algorithm which finds an optimal solution in the case of integer values of the components of the vectors in the input set and fixed space dimension. Bibliogr. 27.
Keywords: bi-partitioning, vector subset, squared Euclidean distances, NP-hardness
Mots-clés : exact pseudopolynomial algorithm. 
@article{DA_2015_22_4_a3,
     author = {A. V. Kel'manov and V. I. Khandeev},
     title = {An exact pseudopolynomial algorithm for a~bi-partitioning problem},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {50--62},
     publisher = {mathdoc},
     volume = {22},
     number = {4},
     year = {2015},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2015_22_4_a3/}
}
TY  - JOUR
AU  - A. V. Kel'manov
AU  - V. I. Khandeev
TI  - An exact pseudopolynomial algorithm for a~bi-partitioning problem
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2015
SP  - 50
EP  - 62
VL  - 22
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2015_22_4_a3/
LA  - ru
ID  - DA_2015_22_4_a3
ER  - 
%0 Journal Article
%A A. V. Kel'manov
%A V. I. Khandeev
%T An exact pseudopolynomial algorithm for a~bi-partitioning problem
%J Diskretnyj analiz i issledovanie operacij
%D 2015
%P 50-62
%V 22
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2015_22_4_a3/
%G ru
%F DA_2015_22_4_a3
A. V. Kel'manov; V. I. Khandeev. An exact pseudopolynomial algorithm for a~bi-partitioning problem. Diskretnyj analiz i issledovanie operacij, Tome 22 (2015) no. 4, pp. 50-62. http://geodesic.mathdoc.fr/item/DA_2015_22_4_a3/

[1] A. A. Ageev, A. V. Kel'manov, A. V. Pyatkin, “NP-hardness of the Euclidean max-cut problem”, Dokl. Math., 89:3 (2014), 343–345 | DOI | DOI | MR | Zbl

[2] A. E. Baburin, E. Kh. Gimadi, N. I. Glebov, A. V. Pyatkin, “The problem of finding a subset of vectors with the maximum total weight”, J. Appl. Ind. Math., 2:1 (2008), 32–38 | DOI | MR | Zbl

[3] A. E. Galashov, A. V. Kel'manov, “A 2-approximate algorithm to solve one problem of the family of disjoint vector subsets”, Autom. Remote Control, 75:4 (2014), 595–606 | DOI | MR | Zbl

[4] E. Kh. Gimadi, Yu. V. Glazkov, I. A. Rykov, “On two problems of choosing some subset of vectors with integer coordinates that has maximum norm of the sum of elements in an Euclidean space”, J. Appl. Ind. Math., 3:3 (2009), 343–352 | DOI | MR | Zbl

[5] E. Kh. Gimadi, A. V. Kel'manov, M. A. Kel'manova, S. A. Khamidullin, “A posteriori detection of a quasiperiodic fragment with a given number of repetitions in a numerical sequence”, Sib. Zh. Ind. Mat., 9:1 (2006), 55–74 | MR | Zbl

[6] E. Kh. Gimadi, A. V. Pyatkin, I. A. Rykov, “On polynomial solvability of some problems of a vector subset choice in a Euclidean space of fixed dimension”, J. Appl. Ind. Math., 4:1 (2010), 48–53 | DOI | MR | Zbl

[7] A. V. Dolgushev, A. V. Kel'manov, “On the algorithmic complexity of a problem in cluster analysis”, J. Appl. Ind. Math., 5:2 (2011), 191–194 | DOI | MR | Zbl

[8] A. V. Dolgushev, A. V. Kel'manov, “An approximation algorithm for solving a problem of cluster analysis”, J. Appl. Ind. Math., 5:4 (2011), 551–558 | DOI | MR | Zbl

[9] A. V. Dolgushev, A. V. Kel'manov, V. V. Shenmaier, “A polynomial approximation scheme for a problem of cluster analysis”, Doklady 9th Int. Conf. “Intellectualization of Information Processing” (Budva, Montenegro, Sept. 16–22, 2012), Torus Press, Moscow, 2012, 242–244

[10] I. I. Eremin, E. Kh. Gimadi, A. V. Kel'manov, A. V. Pyatkin, M. Yu. Khachai, “2-Approximation algorithm for finding a clique with minimum weight of vertices and edges”, Proc. Steklov Inst. Math., 284, Suppl. 1, 2014, S87–S95 | DOI | Zbl

[11] A. V. Kel'manov, “Off-line detection of a quasi-periodically recurring fragment in a numerical sequence”, Proc. Steklov Inst. Math., 263, Suppl. 2, 2008, S84–S92 | MR | Zbl

[12] A. V. Kel'manov, “On the complexity of some data analysis problems”, Comput. Math. Math. Phys., 50:11 (2010), 1941–1947 | DOI | MR | Zbl

[13] A. V. Kel'manov, “On the complexity of some cluster analysis problems”, Comput. Math. Math. Phys., 51:11 (2011), 1983–1988 | DOI | MR | Zbl

[14] A. V. Kel'manov, A. V. Pyatkin, “On the complexity of a search for a subset of “similar” vectors”, Dokl. Math., 78:1 (2008), 574–575 | DOI | MR | Zbl

[15] A. V. Kel'manov, A. V. Pyatkin, “Complexity of certain problems of searching for subsets of vectors and cluster analysis”, Comput. Math. Math. Phys., 49:11 (2009), 1966–1971 | DOI | MR | Zbl

[16] A. V. Kel'manov, A. V. Pyatkin, “On complexity of some problems of cluster analysis of vector sequences”, J. Appl. Ind. Math., 7:3 (2013), 363–369 | DOI | MR | Zbl

[17] A. V. Kel'manov, S. M. Romanchenko, S. A. Khamidullin, “Accurate pseudopolynomial-time algorithms for some NP-hard problems of searching for a vector subsequence”, Zh. Vychisl. Mat. Mat. Fiz., 53:1 (2013), 143–153 | DOI | Zbl

[18] A. V. Kel'manov, V. I. Khandeev, “A 2-approximation polynomial algorithm for a clustering problem”, J. Appl. Ind. Math., 7:4 (2013), 515–521 | DOI | MR | Zbl

[19] A. V. Kel'manov, V. I. Khandeev, “A randomized algorithm for two-cluster partition of a set of vectors”, Comput. Math. Math. Phys., 55:2 (2015), 330–339 | DOI | DOI | MR | Zbl

[20] Aloise D., Deshpande A., Hansen P., Popat P., “NP-hardness of Euclidean sum-of-squares clustering”, Mach. Learn., 75:2 (2009), 245–248 | DOI

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

[22] Garey M. R., Johnson D. S., Computers and intractability: a guide to the theory of NP-completeness, Freeman, San Francisco, CA, 1979, 314 pp. | MR | Zbl

[23] Hansen P., Jaumard B., “Cluster analysis and mathematical programming”, Math. Program., Ser. A, 79 (1997), 191–215 | MR | Zbl

[24] Hansen P., Jaumard B., Mladenovich N., “Minimum sum of squares clustering in a low dimensional space”, J. Classif., 15:1 (1998), 37–55 | DOI | MR | Zbl

[25] Inaba M., Katoh N., Imai H., “Applications of weighted Voronoi diagrams and randomization to variance-based $k$-clustering”, Proc. 10th Symp. Comput. Geom. (Stony Brook, NY, June 6–8, 1994), ACM, New York, 1995, 332–339

[26] MacQueen J. B., “Some methods for classification and analysis of multivariate observations”, Proc. 5th Berkeley Symp. Math. Stat. Probab., v. 1, Univ. California Press, Berkeley, CA, 1967, 281–297 | MR | Zbl

[27] Rao M. R., “Cluster analysis and mathematical programming”, J. Amer. Stat. Assoc., 66 (1971), 622–626 | DOI | Zbl