Introduction

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.

Problems Formulation

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 = {y 1 , . . . , y N } of points from R q and number α ∈ (0, 1). Find : a subset C ⊂ Y with the largest cardinality such that ∑ 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

∑ y∈C ∥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 = {y 1 , . . . , y N } of points (vectors) from R q and a number α ∈ (0, 1). Find : a subset C ⊂ Y with the largest cardinality such that

1 |C| ∑ y∈C y 2 ≤ α 1 |Y| ∑ y∈Y y 2 .

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 1 |C| ∥ ∑ y∈C y∥ 2 . Problem 3 (Cardinality-weighted variance-based 2-clustering with given center ).

Given: a set Y = {y 1 , . . . , y N } of points from R q and a positive integer M .

Find : a partition of Y into two clusters C and Y \ C such that |C| ∑ y∈C ∥y − y(C)∥ 2 + |Y \ C| ∑ y∈Y\C ∥y∥ 2 −→ min 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 ( √ 2q ε + 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 R q , 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

w 1 ∑ y∈C ∥y − y(C)∥ 2 + w 2 ∑ y∈Y\C ∥y∥ 2 subject to constraint |C| = M .

In [Kel'manov et al., 2017], an approximation algorithm is constructed. It allows to find a (1+ε)-approximate solution of the problem for an arbitrary ε ∈ (0, 1) in O

( qN 2 ( √ 2q ε + 2 ) q ) time.

Moreover, in the same paper, the modification of this algorithm with improved running time of

O ( √ qN 2 ( πe 2 ) q/2 ( 1 √ ε +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+ 1 √ ε ))

) 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 R q and a positive ineger

K ≥ 2. Find : a partition of Y into clusters C 1 , . . . , C K minimizing the value of K ∑ k=1 1 |C k | − 1 ∑ y∈C k ∥y − y(C k )∥ 2 , where y(C k ) is a centroid of cluster C k .

Problem 6 (Normalized K-Means clustering with a given center ).

Given:

a set Y of N points in R d and a positive ineger K ≥ 2. Find : a partition of Y into clusters C 1 , . . . , C K minimizing the value of K−1 ∑ k=1 1 |C k | − 1 ∑ y∈C k ∥y − y(C k )∥ 2 + 1 |C K | − 1 ∑ y∈CK ∥y∥ 2 , where y(C k ) is a centroid of cluster C k .

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 = {y 1 , . . . , y N } of points from R q and a positive integer J > 1.

Find : a partition of Y into nonempty clusters C 1 , . . . , C J such that J ∑ j=1 1 |C j | ∑ y∈Cj y 2 −→ min .

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 = {y 1 , . . . , y N } of points from R q and a positive integer J > 1.

Find : a partition of Y into nonempty clusters C 1 , . . . , C J such that

J ∑ j=1 ∑ y∈Cj y 2 −→ min .

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 = {y 1 , . . . , y N } of points from R q and a positive integer J > 1.

Find : a partition of Y into nonempty clusters C 1 , . . . , C J such that J ∑ j=1 ∑ y∈Cj 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 [Kel'manov & Pyatkin, 2016], [Eremeev et al, 2016], [Kel'manov & Pyatkin, 2009].

Problem 10 (Finding a subsequence in a sequence) Given: a sequence Y = (y 1 , . . . , y N ) of points from R q and positive integer numbers T min , T max and M > 1.

Find : a tuple M = (n 1 , . . . , n M ), where n m ∈ N = {1, . . . , N }, m = 1, . . . , N , such that

∑ j∈M ∥y j − y(M)∥ 2 → min,

where

y(M) = 1 |M| ∑ i∈M y i is a geometric center (centroid) of the subsequence {y i ∈ Y | i ∈ M} subject to constraints T min ≤ n m − n m−1 ≤ T max ≤ N, m = 2, . . . , M,(1)

on the elements of the tuple (n 1 , . . . , n M ). 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 T min and T max are parameters is analyzed in [Kel'manov & Pyatkin, 2013]. In this work the authors showed that this problem is strongly NP-hard for any T min < T max . In the trivial case when T min = T max 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 (T max − T min + 1) + q)( √ 2q ε + 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 = (y 1 , . . . , y N ) of points from R q , and some positive integer numbers T min , T max , and M . Find: a tuple M = (n 1 , . . . , n M ), where n m ∈ N = {1, . . . , N }, m = 1, . . . , N , such that

∑ j∈M ∥y j − y(M)∥ 2 + ∑ j∈N \M ∥y j ∥ 2 → min,

where y(M) = 1 M ∑ i∈M y i , under constraints (1) on the elements of (n 1 , . . . , n M ). A special case of Problem 11 where T min = 1 and T max = 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 T min and T max are the parameters was analyzed. In the cited work it was shown that Problem 11 is strongly NP-hard for any T min < T max . In the trivial case when T min = T max , 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 = (y 1 , . . . , y N ) of points from R q and some positive integers T min , T max , L, and M .

Find : nonempty disjoint subsets M 1 , . . . , M L of N = {1, . . . , N } such that L ∑ l=1 ∑ j∈M l ∥y j − y(M l )∥ 2 + ∑ i∈N \M ∥y i ∥ 2 → min,(2)

where M = ∪ L l=1 M l , and y(M l ) = 1 |M l | ∑ j∈M l y j is the centroid of subset {y j | j ∈ M l }, under the following constraints:

(1) the cardinality of M is equal to M , (2) concatenation of elements of subsets M 1 , . . . , M L is an increasing sequence, provided that the elements of each subset are in ascending order,

(3) the inequalities (1) for the elements of M = {n 1 , . . . , n M } are satisfied.

Problem 13 (Minimum sum-of-squares clustering problem on sequence with given center of one cluster ).

Given: a sequence Y = (y 1 , . . . , y N ) of points from R q and some positive integers T min , T max , and L. Find : nonempty disjoint subsets M 1 , . . . , M L of N = {1, . . . , N } minimizing (2) under the following constraints:

(1) concatenation of elements of subsets M 1 , . . . , M L is an increasing sequence, provided that the elements of each subset are in ascending order,

(2) the inequalities (1) for the elements of M = {n 1 , . . . , n M } are satisfied (the cardinality of M assumed to be unknown).

In [Kel'manov & Pyatkin, 2013], the variants of Problems 12, 13 in which T min and T max 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 T min < T max . In the trivial case when T min = T max , 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.