We consider some poorly studied clustering problems. The paper purpose is to present a short survey on some new results on the computational complexity of these problems, and on efficient algorithms with performance guarantees for their solutions. The subject of this study is several related discrete optimization problems of partitioning (clustering) a finite set and a finite sequence of Euclidean points into a family of clusters. Our goal is to review some recent (2016-2017) results of the author together with his colleagues and students (from Sobolev Institute of Mathematics and Novosibirsk State University) on these problems. We present the results on the computational complexity of the problems under consideration and on the efficient approximation algorithms for their solution. Our research is motivated by the insufficient studies of the problems and by their importance, in particular, for computer geometry, statistics, physics, mathematical problems of clustering, pattern recognition, machine learning, data mining.
Introduction Throughout this paper, R denotes the set of real numbers and ∥·∥ is the Euclidean norm. The following problems are considered.
Problem 1 (Subset of points with the largest cardinality under constraint on the total quadratic variation ). Given: a set Y = {y1; : : : ; yN } of points from Rq and number ∈ (0; 1).
Find : a subset C ⊂ Y with the largest cardinality such that ∑ ∥y − y(C)∥2 ≤
∑ ∥y − y(Y)∥2; y2C y2Y where y(C) = jC1j ∑y2C y is the centroid (the geometrical center) of subset C, and y(Y) = jY1 j ∑y2Y y is the centroid of the input set.
The strong NP-hardness of Problem 1 was proved in [Ageev et al., 2017] and in the same paper a polynomialtime 1/2-approximation algorithm with O(N 2(q + log N )) running time was proposed.
These results supplement and develop the results obtained in [Aggarwal et al., 1991], [Kel’manov & Pyatkin, 2011], [Shenmaier, 2016], [Kel’manov & Romanchenko, 2011], [Shenmaier, 2012], [Kel’manov & Romanchenko, 2012], [Kel’manov & Romanchenko, 2014] for M -Variance problem. In this problem we need to find a subset C with given cardinality in N -element set Y of points minimizing the value of ∑y2C ∥y − y(C)∥2.
Problem 2 (Subset of vectors with the largest cardinality under constraint on normalized length of vectors sum).
Given: a set Y = {y1; : : : ; yN } of points (vectors) from Rq and a number ∈ (0; 1).
Find : a subset C ⊂ Y with the largest cardinality such that 1 |C| y2C ∑ y 2 ≤ 1
2 ∑ y : |Y| y2Y
In [Eremeev et al., 2017], it was shown that Problem 2 is NP-hard even in terms of finding a feasible solution. An exact algorithm for the case of integer components of the input vectors is proposed in the same paper. The algorithm has a pseudo-polynomial time complexity if the dimension q of the space is bounded from above by a constant.
These results supplement and develop the results obtained in [Eremeev et al, 2016] for another subset searching problem. In this problem we have to find a subset C ⊆ Y minimizing the value of jC1j ∥ ∑y2C y∥2.
Problem 3 (Cardinality-weighted variance-based 2-clustering with given center ).
Given: a set Y = {y1; : : : ; yN } of points from Rq and a positive integer M .
Find : a partition of Y into two clusters C and Y \ C such that |C| ∑ ∥y − y(C)∥2 + |Y \ C| ∑ ∥y∥2 −→ min y2C y2YnC subject to constraint |C| = M .
The strong NP-hardness of Problem 3 was proved in [Kel’manov & Pyatkin, 2015], [Kel’manov & Pyatkin, 2016]. In the same papers, the nonexistence of an FPTAS (Fully Polynomial-Time Approximation Scheme) was shown (unless P=NP) for this problem.
In [Kel’manov & Motkova, 2016], an exact algorithm for the case of integer components of the input points was presented. If the dimension q of the space is bounded by a constant, then this algorithm has a pseudopolynomial complexity and the running time of the algorithm is O(N (M B)q), where B is the maximum absolute coordinate value of the points.
An approximation algorithm that allows to find a (1 + ")-approximate solution in O(qN 2(√ 2"q + 2)q) time for a given relative error " was proposed in [Kel’manov & Motkova, 2016]. If the space dimension is bounded by a constant, then this algorithm implements an FPTAS with O(N 2(1=")q=2) running time.
Following Problem 4 is a generalization of Problem 3.
Problem 4 (Weighted variance-based 2-clustering with given center ).
Given: an N -element set Y of points from Rq, a positive integer M ≤ N , and real numbers (weights) !1 > 0 and !2 ≥ 0.
Find : a partition of Y into two clusters C and Y\C minimizing the value of w1∑ ∥y − y(C)∥2 + w2 ∑ ∥y∥2 y2C y2YnC solution of the problem for an arbitrary " ∈ (0; 1) in O subject to constraint |C| = M .
In [Kel’manov et al., 2017], an approximation algorithm is constructed. It allows to find a (1 + ")-approximate ( q)
time. Moreover, in the same paper, qN 2(√ 2"q + 2) the modification of this algorithm with improved running time of O(√qN 2(2e )q=2(p1" + 2)q) was proposed. The algorithm implements an FPTAS for the fixed space dimension. If the dimension of space is bounded by C log n, where C is a positive constant, the algorithm remains polynomial and implements a PTAS (Polynomial-Time Approximation Scheme) with O (N C (1:05+log(2+ p1" ))) running time.
These results supplement and develop the results obtained in [Kel’manov & Pyatkin, 2015], [Kel’manov & Pyatkin, 2016], [Kel’manov & Motkova, 2016], [Kel’manov & Motkova, 2016] for Problem 3.
The complexity status of following Problems 5–9 seemed to be unclear up to now.
Problem 5 (Normalized K-means clustering ).
Given: a set Y of N points in Rq and a positive ineger K ≥ 2.
Find : a partition of Y into clusters C1; : : : ; CK minimizing the value of
K ∑
1 k=1 |Ck| − 1 y2Ck
∑ ∥y − y(Ck)∥2; where y(Ck) is a centroid of cluster Ck.
Problem 6 (Normalized K-Means clustering with a given center ).
Given: a set Y of N points in Rd and a positive ineger K ≥ 2.
Find : a partition of Y into clusters C1; : : : ; CK minimizing the value of
K 1 ∑
1 k=1 |Ck| − 1 y2Ck ∑ ∥y − y(Ck)∥2 +
1 |CK | − 1 y2CK ∑ ∥y∥2; where y(Ck) is a centroid of cluster Ck.
In [Ageev, 2017], it was proved that Problem 5 is strongly NP-hard for each fixed K ≥ 3 and Problem 6 is strongly NP-hard for each fixed K ≥ 4.
Problem 7 (Minimum sum of normalized squares of norms clustering ).
Given: a set Y = {y1; : : : ; yN } of points from Rq and a positive integer J > 1.
Find : a partition of Y into nonempty clusters C1; : : : ; CJ such that
In this problem the criterion is minimizing the sum over all clusters of normalized by the cardinality squared norms of the sum of cluster elements.
Problem 8 (Minimum sum of squared norms clustering ).
Given: a set Y = {y1; : : : ; yN } of points from Rq and a positive integer J > 1.
Find : a partition of Y into nonempty clusters C1; : : : ; CJ such that
In this problem the criterion is minimizing the sum over all clusters of squared norms of the sum of cluster elements.
Problem 9 (Minimum sum-of-norms clustering ).
Given: a set Y = {y1; : : : ; yN } of points from Rq and a positive integer J > 1.
Find : a partition of Y into nonempty clusters C1; : : : ; CJ such that ∑J 1 j=1 |Cj | y2Cj ∑ y 2
−→ min : J ∑ j=1 y2Cj ∑ y 2
−→ min : J ∑ j=1 y2Cj ∑ y
−→ min : In this problem the criterion is minimizing the sum over all clusters of norms of the sum of cluster elements.
It is proved [Kel’manov & Pyatkin, 2016] that problems 7–9 are strongly NP-hard if the number of clusters is a part of the input, and NP-hard in the ordinary sense if the number of clusters is not a part of the input (is fixed). Moreover, the problems are NP-hard even in the case of dimension 1 (on a line).
These results supplement and develop the results obtained in [Eremeev et al, 2016], [Kel’manov & Pyatkin, 2009].
Problem 10 (Finding a subsequence in a sequence) Given: a sequence Y = (y1; : : : ; yN ) of points from Rq and positive integer numbers Tmin, Tmax and M > 1. Find : a tuple M = (n1; : : : ; nM ), where nm ∈ N = {1; : : : ; N }; m = 1; : : : ; N , such that ∑ ∥yj − y(M)∥2 → min; j2M where y(M) = constraints jM1 j ∑i2M yi is a geometric center (centroid) of the subsequence {yi ∈ Y | i ∈ M} subject to Tmin ≤ nm − nm 1 ≤ Tmax ≤ N; m = 2; : : : ; M; (1) on the elements of the tuple (n1; : : : ; nM ).
Problem 10 is among poorly studied strongly NP-hard discrete optimization problems. By this time for Problem 10 the following results were obtained. First, we should note that there are neither exact polynomialtime, nor pseudo-polynomial-time algorithms or FPTAS schemes, unless P=NP.
The case of Problem 10 when Tmin and Tmax are parameters is analyzed in [Kel’manov & Pyatkin, 2013]. In this work the authors showed that this problem is strongly NP-hard for any Tmin < Tmax. In the trivial case when Tmin = Tmax this problem can be solved through a polynomial time.
In [Kel’manov et al., 2012] a 2-approximation polynomial-time algorithm is proposed; the running time of the algorithm is O(N 2(M N + q)).
In the case of Problem 10 with integer components of the sequence elements and fixed dimension q of the space in [Kel’manov et al., 2013] an exact pseudo-polynomial-time algorithm is substantiated. This algorithm finds an optimal solution of Problem 10 in O(N 3(M D)q) time.
The main result of [Kel’manov et al., 2016] is an approximation algorithm which allows to find a (1 + ")– approximate solution for any " > 0 in O(N 2(M (Tmax − Tmin + 1) + q)(√ 2"q + 2)q) time. If the dimension q of the space is fixed then the time complexity of this algorithm is equal to O(M N 3(1=")q=2), and it implements an FPTAS.
Problem 11 (Minimum sum-of-squares 2-clustering problem on sequence with given center of one cluster ). Given: a sequence Y = (y1; : : : ; yN ) of points from Rq, and some positive integer numbers Tmin, Tmax, and M . Find: a tuple M = (n1; : : : ; nM ), where nm ∈ N = {1; : : : ; N }; m = 1; : : : ; N , such that ∑ ∥yj − y(M)∥2 + j2M
∑ j2N nM ∥yj ∥2 → min; where y(M) = M1 ∑i2M yi, under constraints (1) on the elements of (n1; : : : ; nM ).
A special case of Problem 11 where Tmin = 1 and Tmax = N is equivalent [Kel’manov & Pyatkin, 2013] to the strongly NP-hard problem of partitioning a set [Kel’manov & Pyatkin, 2009], which does not admit [Kel’manov & Khandeev, 2016] FPTAS unless P = NP. In other words, Problem 11 of partitioning a sequence is the generalization of the strongly NP-hard problem of partitioning a set. Therefore, according to [Garey & Johnson, 1979], Problem 11 also admits neither exact polynomial, nor exact pseudopolynomial algorithms, nor FPTAS unless P = NP.
In [Kel’manov & Pyatkin, 2013], the variant of Problem 11 in which Tmin and Tmax are the parameters was analyzed. In the cited work it was shown that Problem 11 is strongly NP-hard for any Tmin < Tmax. In the trivial case when Tmin = Tmax, the problem is solvable in polynomial time.
A 2-approximation algorithm for Problem 11 with O(N 2(M N + q)) running time was presented in [Kel’manov & Khamidullin, 2014].
Special cases of the problem were studied in [Kel’manov et al., 2017a], [Kel’manov et al., 2016]. In [Kel’manov et al., 2017a], for the case of integer inputs and fixed space dimension q, an exact pseudopolynomial algorithm was proposed. The running time of the algorithm is O(N 3(M D)q), where D is the maximal absolute value of the coordinates of input points. For the case with fixed space dimension in [Kel’manov et al., 2016] an FPTAS was constructed which, given a relative error ", finds a (1 + ")-approximate solution of Problem 11 in O(M N 3(1=")q=2) time.
The new result [Kel’manov et al., 2017b] is a randomized algorithm for Problem 11. For an established parameter value, given " > 0 and fixed ∈ (0; 1), this algorithm allows to find a (1 + ")-approximate solution of the problem with a probability of at least 1 − in O(qM N 2) time. The conditions are established under which the algorithm is asymptotically exact and its time complexity is O(qM N 3).
Problem 12 (Minimum sum-of-squares clustering problem on sequence with given center of one cluster and cluster cardinalities ).
Given: a sequence Y = (y1; : : : ; yN ) of points from Rq and some positive integers Tmin, Tmax, L, and M . Find : nonempty disjoint subsets M1; : : : ; ML of N = {1; : : : ; N } such that
L ∑ ∑ ∥yj − y(Ml)∥2 + cwohnesrteraMints=: ∪lL=1Ml, and y(Ml) = jM1 lj ∑j2Ml yj is the centroid of subset {yj | j ∈ Ml}, under the following (1) the cardinality of M is equal to M , (2) concatenation of elements of subsets M1; : : : ; ML is an increasing sequence, provided that the elements of each subset are in ascending order, (3) the inequalities (1) for the elements of M = {n1; : : : ; nM } are satisfied.
Problem 13 (Minimum sum-of-squares clustering problem on sequence with given center of one cluster ). Given: a sequence Y = (y1; : : : ; yN ) of points from Rq and some positive integers Tmin, Tmax, and L.
Find : nonempty disjoint subsets M1; : : : ; ML of N = {1; : : : ; N } minimizing (2) under the following constraints:
(1) concatenation of elements of subsets M1; : : : ; ML is an increasing sequence, provided that the elements of each subset are in ascending order,
(2) the inequalities (1) for the elements of M = {n1; : : : ; nM } are satisfied (the cardinality of M assumed to be unknown).
In [Kel’manov & Pyatkin, 2013], the variants of Problems 12, 13 in which Tmin and Tmax are the parameters was analyzed. In the cited work it was shown that both parameterized variants of the problems are strongly NP-hard for any Tmin < Tmax. In the trivial case when Tmin = Tmax, the problems are solvable in polynomial time.
Except for the case with L = 1 in equation (2), no algorithms with guaranteed approximation factor were known up to 2016 for Problem 11. This case is equivalent to Problem 12. For this problem, the existing results are listed above.
The new result of [Kel’manov et al., 2016] is an algorithm that allows to find a 2-approximate solution of the problem in O(LN L+1(M N + q)) time, which is polynomial if the number L of clusters with unknown centroids is fixed.
For Problem 13, except for the case with L = 1 in equation (2), no algorithms with guaranteed approximation factor were known up to 2017. For this special case, in [Kel’manov & Khamidullin, 2015], a 2-approximation polynomial-time algorithm with O(N 2(N + q)) running time was presented.
The new result of [Kel’manov et al., 2017c] is an algorithm that allows to find a 2-approximate solution of the problem in O(LN L+1(N + q)) time, which is polynomial if the number L of clusters with unknown centroids is fixed.
Acknowledgements The study of problems 1–3, 5, 6, 10, 11 and 12 was supported by the the Russian Foundation for Basic Research (projects 15-01-00462, 16-31-00186, 16-07-00168), and by the Ministry of Science and Education of the Russian Federation under the 5-100 Excellence Programme. The study of problems 4, 7–9 and 13 was supported by the Russian Science Foundation (project 16-11-10041).