Introduction

In this work, we consider a strongly NP-hard problem of discrete optimization. The goal of our work is to present a short survey on the results for these problems.

The problem under study is closely related to the well-known strongly NP-hard The main difference between the problem under study and this problem is that in the considered problem the center of one of the clusters is fixed in the origin (without loss of generality). It is obvious, that the considered problem and the Weighted variance-based 2-clustering problem are not equivalent and so both of them need an individual study. The importance of the problem for applications motivates to continue researches, e.g. importance for geometric problems, approximation problems, statistical problems of joint evaluations and testing hypotheses by nonuniform samples, problems of Data clustering, Data mining, Machine learning, Big data, applied problems in technical and medical diagnostics, etc.

Cardinality-weighted Variance-based 2-clustering with Given Center

Problem 1. 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 non-empty clusters C and Y \ C such that

F 1 (C) = |C| ∑ y∈C ∥y − y(C)∥ 2 + |Y \ C| ∑ y∈Y\C ∥y∥ 2 −→ min , (1)

where

y(C) = 1 |C| ∑ y∈C y is the geometric center (centroid) of C and such that |C| = M .

Problem 1 is strongly NP-hard [Kel'manov & Pyatkin, 2015, Kel'manov & Pyatkin, 2016]. Therefore, by [Garey & Johnson, 1979], there are neither exact polynomial-time nor exact pseudopolynomial-time algorithms for this problem, unless P=NP.

Despite of this, a pseudopolynomial algorithm for the special case of Problem 1 exists. It proposed in [Kel'manov & Motkova, 2016a] and finds an optimal solution in the case of integer components of the points in the input set and fixed space dimension.

Algorithm A 1 (exact pseudopolynomial algorithm).

Input: A set Y and some positive integer M ≤ N .

Step 1. Construct G -a multidimensional cubic uniform in each coordinate grid of size 2D with the distance 1 M between the nodes and the center at the origin, and D is the maximal modulus of the coordinates of input points.

Step 2. For each node x ∈ G, calculate

g x (y) = (2M − N )∥y∥ 2 − 2M ⟨y, x⟩ , y ∈ Y;

(2) find the subset B x which consists of M points of the set Y, at which the function g x (y) has the smallest values.

Calculate F 1 (B x ) by (1).

Step 3. In the family In the case of fixed space dimension q the algorithm is pseudopolynomial.

F 1 (B x ), x ∈ G constructed at Step 2, find the node x A1 = arg min x∈G F 1 (B x

In [Kel'manov & Pyatkin, 2015, Kel'manov & Pyatkin, 2016] it is also shown that for Problems 1 there does not exist any fully polynomial time approximation scheme (FPTAS), unless P=NP. In [Kel'manov & Motkova, 2016b] was proposed such approximation scheme for a special case of the Problem 1 when the space dimension q is fixed.

Algorithm A 2 (approximation scheme).

Input: a set Y and numbers M and ε.

For each point y ∈ Y Steps 1-6 are executed.

Step 1. Compute the values g y (z), z ∈ Y, using formula (2); find a subset B y ⊆ Y with M smallest values g y (z), compute F (B y ) using formula (1).

Step 2. If F (B y ) = 0, then put C A3 = B y ; exit.

Step 3.

Compute H = H(y) = 1 M √ F 1 (B y ) and h = h(y, ε) = 1 M √ 2ε q F 1 (B y ). Step 4. Construct the lattice G(y, h, H + h/2) using formula G(y, h, H + h/2) = {d ∈ R q | d = y + h • (i 1 , . . . , i q ), i k ∈ Z, |hi k | ≤ H + h/2, k ∈ {1, . . . , q}}.

Step 5. For each node x of the lattice G(y, h, H + h/2) compute the values g x (y), y ∈ Y, using formula (2) and find a subset B x ⊆ Y with M smallest values g x (y). Compute F 1 (B x ) using formula (1), remember this value and the set B x .

Step 6. If F (B x ) = 0, then put C A2 = B x ; exit.

Step 7. In the family ) q ) time.

{B x | x ∈ G(y, h, H + h/2),

Corollary 1. In the case when the dimension q of space is bounded by a constant value, this algorithm is an FPTAS.

Later in [Kel'manov et al., 2017] was proposed the similar approximation scheme with the same time complexity for the generalization of Problem 1 in which the weight factors are given as input (positive real numbers). Also there was presented an improved algorithm that allows to find (1 + ε)-approximate solution of generalized

problem in O ( √ qN 2 ( πe 2 ) q/2 (√ 2 ε + 2 ) q )

time. In the case when the dimension q of space is bounded by a constant value, this algorithm is also an FPTAS. In addition, improved algorithm remains polynomial even when the dimension q of the space is bounded by the value C log N , where C is the positive constant. It is clear that in this case algorithm implements a PTAS with time complexity N O(log 1 ε ) . The last proposed algorithm for Problem 1 until this moment is a 2-approximation algorithm. It was proposed in [Kel'manov & Motkova, 2017] and allows us to find an approximate solution in the polynomial time.

Algorithm A 3 (2-approximation algorithm).

Input: N -elements set Y ⊂ R q , natural number M ≤ N.

For each point y ∈ Y Steps 1-2 are executed.

Step 1. Compute the values g y (z), z ∈ Y, using formula (2); find an M -elements subset B y ⊆ Y with the smallest values g y (z), compute F 1 (B y ) using formula (1).

Step 2. If F 1 (B y ) = 0, then put C A2 = B y ; exit.

Step 3. In the family {B y |, y ∈ Y} of candidate sets that have been constructed in Steps 1-2, choose as a solution C A3 the set B x , for which F 1 (B x ) is minimal.

Output: the set C A3 . Two examples of an input set (of 1000 points) and admissible solutions (i.e. 300-elements subset B y ) found by Algorithm A 3 at step 1 are presented at Fig. 1 Let us substuntiate this algorithm below.

The following two lemmas are well known.

(see, for example, [Kel'manov & Romanchenko, 2012, Kel'manov & Romanchenko, 2014]).

Lemma 1. For an arbitrary point x ∈ R q , a finite set Z ⊂ R q and z = 1

|Z| ∑ z∈Z z (z is the centroid of Z), it is true that ∑ z∈Z ∥z − x∥ 2 = ∑ z∈Z ∥z − z∥ 2 + |Z| • ∥x − z∥ 2 .

Lemma 2. For a finite set Z ⊂ R q , if a point u ∈ R q is closer (in terms of distance) to the centroid z of Z than any point in Z, then

∑ z∈Z ∥z − u∥ 2 ≤ 2 ∑ z∈Z ∥z − z∥ 2 . Lemma 3. Let S(C, x) = |C| ∑ y∈C ∥y − x∥ 2 + |Y \ C| ∑ y∈Y\C ∥y∥ 2 , C ⊆ Y, x ∈ R q .

Then the next statements are true:

(1) for any nonempty fixed set C ⊆ Y the minimum of the function S(C, x) over x ∈ R q is reached at the point

y(C) = 1 |C| ∑ y∈C y;

(2) if |C| = M = const, then for any fixed point x ∈ R q the minimum of function S(C, x) over C ⊆ Y is reached at the subset B x that consists of M points of the set Y, at which the function (2) has the smallest values.

Proof. The first statement follows from Lemma 2 and the definition of the functions S and F . Since |Y| = N and |C| = M , the second statement follows from the next chain of equalities:

S(C, x) = M ∑ y∈C ∥y − x∥ 2 + (N − M ) ∑ y∈Y\C ∥y∥ 2 = M ∑ y∈C ∥y∥ 2 − 2M ∑ y∈C ⟨y, x⟩ + M 2 ∥x∥ 2 + (N − M ) ( ∑ y∈Y ∥y∥ 2 − ∑ y∈C ∥y∥ 2 ) = ∑ y∈C { (2M − N )∥y∥ 2 − 2M ⟨y, x⟩ } + M 2 ∥x∥ 2 + (N − M ) ∑ y∈Y ∥y∥ 2 .

It remains to note that in the last two equalities the last two addends do not depend on C. Lemma is proved. Theorem 3. An Algorithm A 3 finds a 2-approximate solution of Problem 1 in time O ( qN 2 ) . Proof. Let C * be an optimal subset and t = arg min y∈C * ||y − y(C * )|| 2 be a point from a subset C * that is the closest to its centroid.

Step-by-step, the algorithm goes through every points y of the set Y. Since t ∈ Y, a permissible solution also will be formed for the point t: the subset B t , defined by Lemma 3 (if x = t).

Besides, a value F (B t ) of objective function for the Problem 1 will be calculated. For this value we have this inequalities from definitions of the functions F and S and Lemma 3 and a definition of the point t:

F (B t ) = S y(B t ) (B t ) ≤ S t (B t ) ≤ S t (C * ).

(3)

Applying Lemma 2 to the set Z = C * and the point u = t, we have

∑ y∈C * ||y − t|| 2 ≤ 2 ∑ y∈C * ||y − y(C * )|| 2 .

Using this inequality and definition (2), we find an estimation for a right part of (3)

S t (C * ) = M ∑ y∈C * ||y − t|| 2 + (N − M ) ∑ y∈Y\C * ||y|| 2 ≤ 2M ∑ y∈C * ||y − y(C * )|| 2 + (N − M ) ∑ y∈Y\C * ||y|| 2 ≤ 2F (C * ). (4)

Combining ( 3) and (4), we have

F (B t ) ≤ 2F (C * ). (5)

From

Step 3 we know that the algorithm finds a solution of Problem 1 in the next form:

C A = arg min y∈Y F (B y ).(6)

Since B t ∈ {B y |y ∈ Y}, from (6) we have an inequality

F (C A ) ≤ F (B t ).(7)

Finally, ( 5) and ( 7) implies an estimate

F (C A ) ≤ 2F (C * ). (8

Conclusion

In this work, we presented a short survey on the results for the problem of 2-partitioning of points in Euclidean space into two clusters. Also we presented the new result: a 2-approximation algorithm.

It seems important to continue studying and the issue of great interest is the substantiation of randomized algorithms for this problem with linear or sub-linear time complexity.