In the problem considered, it is required to minimize the sum of elements chosen in a family of nite numerical sequences with some constraints on the choice of elements. Namely, given a family of L nonnegative N -element sequences and a positive integer J , we need to minimize the sum of J intra-sums each of which includes only one element in every input sequence with all possible L-permutations of these sequences and under some constraints on the choice of elements to be included in the general double sum. The problem is related, for example, to the distant noise-prove monitoring of several moving objects with possible arbitrary displacements (permutations) of these objects. For this problem we present an exact polynomial-time algorithm with O(N 5) running time.
In the paper we study one problem of optimal summing of elements chosen in a family of nite numerical sequences. The subject of this research is algorithmic approximability of the problem. Our goal is to construct an e cient algorithm with the guaranteed accuracy for this problem.
The research is motivated by the absence of available algorithmic results for the problem under consideration and the importance of the problem, in particular, in the distant monitoring of some objects (see next Section). Moreover, the problem considered is a generalization of the Earlier Studied Optimization Problem (see Next Section). This is another reason for this problem to be studied.
The paper has the following structure. Section 2 contains the problem formulation, its interpretation and known results for the particular case of the problem.
Copyright c by the paper's authors. Copying permitted for private and academic purposes.
In: S. Belim et al. (eds.): OPTA-SCL 2018, Omsk, Russia, published at http://ceur-ws.org
In the Same Section, We Announce Our Result Obtained. Section 3 contains two auxiliary problems and exact polynomial-time algorithms for them, which are necessary to justify the proposed algorithm. Finally, in Section 4, we present and justify our algorithm. 2
Problem Formulation and Related Problems Everywhere below, R denotes the set of real numbers, R denotes the set of nonnegative real numbers, N denotes the set of positive integer numbers, denotes the permutation on L elements, denotes the set of all possible permutations on L elements, j denotes the j-th permutation, and j (i), j = 1; : : : ; J , i = 1; : : : ; L, denotes the i-th element of the j-th permutation.
We consider the following
Problem 1. Given a family S = nfs1(n); : : : ; sL(n)g si(n) 2 R ; i = 1; : : : ; L; n =
1; : : : ; N o of sequences and a positive integer J such that J L N . Find an
index tuple (n1; : : : ; nJL), where nk 2 f1; : : : ; N g, k = 1; : : : ; J L, and a tuple
( 1; : : : ; J ) of J permutations on L elements such that
(
J S(n1; : : : ; nJL; 1; : : : ; J ) = X
L
X s j(i)(n(j 1)L+i) j=1 i=1 ! min subject to constraints 1 n1 < n2 < : : : < nJL
N :
In the particular case of Problem 1, when j (i) = i for all j = 1; : : : ; J , i = 1; : : : ; L, we need to nd an index tuple (n1; : : : ; nJL) that minimizes the value of
J L
X X si(n(j 1)L+i)
j=1 i=1
under the same constraints (
In the optimization model inducing this particular case [3], each element si(n), n = 1; : : : ; N , i = 1; : : : ; L, is a squared distance between an element yn 2 Rd in a given sample sequence (y1; : : : ; yN ) and a point xi 2 Rd in a given collection fx1; : : : ; xLg of L points (patterns). In other words, the i-th sequence in the family F is the result of comparisons of the i-th point in the collection fx1; : : : ; xLg with each element in the sample sequence (y1; : : : ; yN ).
In the applied problem, the point xi corresponds to the i-th object and the
collection fx1; : : : ; xLg of points (patterns) corresponds to the collection of L
objects, while the sample sequence (y1; : : : ; yN ) corresponds to a time series
obtained as a monitoring (or measurement) result. In the family F , the i-th
sequence corresponds to the result of comparisons of the i-th object in the pattern
collection fx1; : : : ; xLg with each element of time ordered measurement result.
The applied problem can be interpreted (see [3]) as a noise-proof detection of the
given pattern collection fx1; : : : ; xLg of \pulses" repeated J times in the signal
(y1; : : : ; yN ). In the applied problem, all the \pulses" in the collection have the
same \duration" d and di erent forms, whereas in each collection repetition,
there are no \pulses" permutations. The interval nm nm 1, m = 2; : : : ; J L;
between two consecutive \pulses" is not constant, but it is bounded in accordance
with the inequalities (
Problem 1 is induced by a similar but more complex applied problem in
which the \pulses" (objects) in each repeated pattern collection can be arbitrary
reordered. This reordering causes the presence of permutations in the objective
function (
In this paper, we present a polynomial algorithm which nds an optimal solution of Problem 1 in O(N 5) time. 3
Algorithm Foundation
where ni 2 fa; : : : ; b
To solve Problem 1 we need two auxiliary problems with exact polynomial
algorithms. In addition, we need two well-known problems: (
The rst auxiliary problem has the following formulation.
Problem 2. Given a family F = nff1(n); : : : ; fL(n)g fi(n) 2 R ; i = 1; : : : ; L; n = a; : : : ; b 1; L b o of sequences. Find an index tuple (n1; : : : ; nL), a; a; b 2 N 1g, i = 1; : : : ; L, and a permutation 2 such that F (n1; : : : ; nL; ) =
L
X f (i)(ni) ! min ;
i=1
(
n1 < : : : < nL < b :
Let G = (V [ U ; E ; w) be a complete bipartite graph with the vertex parts
V = fva; : : : ; vb 1g and U = fu1; : : : ; ub ag, and let the edge weights be given
as
wvnuj =
fj (n); j = 1; : : : ; L ;
0; j = L + 1; : : : ; b
a ;
(
For every perfect matching P in G de ne a bijection r : fa; : : : ; b 1g ! f1; : : : ; b ag, where fa; : : : ; b 1g and f1; : : : ; b ag are the sets of indices of U and V respectively. Let W (P) be the weight of the perfect matching P = f(vn; ur(n)); n = a; : : : ; b 1g. The following lemma is true.
Lemma 1. Let P = f(vn; ur (n)); n = a; : : : ; b 1g be the minimum weight
perfect matching in G, where r is the optimal bijection. Then in Problem 2, the
optimal tuple (a; b) = (n1; : : : ; nL), and the optimal permutation (a; b) can
be found by the following formulas:
n1 = minfn j r (n) 2 f1; : : : ; Lg; n 2 fa; : : : ; b
1gg ;
ni = minfn j r (n) 2 f1; : : : ; Lg; n 2 fni 1 + 1; : : : ; b
1gg; i = 2; : : : ; L ; (6)
and
The optimal value F (a; b) of the objective function (
F (a; b) = W (P ) : (5) (7) (8)
To prove this lemma we establish the correspondence between an admissible
tuple and a permutation in Problem 2 and the perfect matching in the graph G.
Then we prove that the optimal value of the objective function (
Note that the minimum weight perfect matching in G can be found by a well-known algorithm (see, for example [4]) in the polynomial time.
Thus, we have the following algorithm for auxiliary Problem 2 in a step-bystep form.
Algorithm A1.
INPUT: a family F of sequences.
Step 1. Construct G using (
Step 2. Find the optimal permutation (a; b) and the optimal tuple (a; b) by (5), (6), and (7).
Step 3. Compute W (P ) and F (a; b) by (8).
OUTPUT: the permutation (a; b), the tuple (a; b) = (n1; : : : ; nL), and the value F (a; b).
The following proposition is true.
Proposition 1. Algorithm A1 nds the optimal solution of Problem 2 in O((b a)3) time.
The proof follows immediately from Lemma 1 and well-known time complexity of the algorithm for the problem of searching the minimum weight perfect matching [4].
The second auxiliary problem has the following formulation. Problem 3. Given positive integers L, J , and N such that J L N , a family Q = fq(n; m) 2 R j 1 n < m N +1; L m n N (J 1)L; n; m 2 Ng. Find an index tuple ( 1; : : : ; J+1), where j 2 f1; : : : ; N + 1g, j = 1; : : : ; J + 1, such that
Q( 1; : : : ; J+1) =
J X q( j ; j+1) ! min; j=1 under the following constraints 1 = 1 < : : : <
J+1 = N + 1 ; j+1 j
L; j = 1; : : : ; J : To solve this auxiliary problem we use an algorithm for the well-known Nearest neighbor search problem(see, for example, [2] and [1]). Given a family H = fh(n; m) 2 R j 1 n m N + 1; n; m 2 Ng and a positive integer J . Find an index tuple ( 1; : : : ; J+1), where j 2 f1; : : : ; N + 1g, j = 1; : : : ; J + 1, such that
H( 1; : : : ; J+1) =
J X h( j ; j+1) ! min ; j=1 subject to constraints 1 = 1 2 : : :
J+1 = N + 1 :
As it is known [1], the Nearest neighbor search problem can be solved in O(J N 2) time.
The following lemma is true.
Lemma 2. Let ( 1 ; : : : ; J+1) be the optimal solution of Nearest neighbor search problem with h(n; m) = <>>>>8 q+(1n;;m); nn ==m11;;=::::n::;;+NNL+; :L1:;:+m;m1=;innf;N: : +:;1m; innf+nN+ L (J >>:>> +1; n =m1;=: : n:;+1 +N (J (J1)L1;)L + 1; : : : ; N + 1 ; 1)Lg ; 1; N + 1g ; (11) and H be the optimal value of objective function (10). Then the components of the optimal tuple ( 1; : : : ; J+1) and the optimal value Q of the function (9) can be found by the following formulas i = i ; i = 1; : : : ; J + 1 ;
Q = H : (9) (10) (12)
To prove this lemma we rst verify that the optimal tuple in the Nearest neighbor search problem is an admissible one in Problem 3. Then we show that this tuple is the optimal solution of Problem 3.
Thus, we have the following algorithm for auxiliary Problem 3.
Algorithm A2.
INPUT: positive integers L, J , and a family Q.
Step 1. Find the family H by (11). Compute the optimal value H and nd the optimal tuple ( 1 ; : : : ; J+1) of the Nearest neighbor search problem.
Step 2. Compute the optimal value Q of the objective function of Problem 3 using (13), and nd the optimal tuple ( 1; : : : ; J+1) of indices using (12).
OUTPUT: the tuple ( 1; : : : ; J+1) and the value Q .
The following proposition is true.
Proposition 2. Algorithm A2 nds an optimal solution of Problem 3 in O(J N 2) time.
The validity of Proposition 2 follows from Lemma 2 and time complexity of the algorithm for the Nearest neighbor search problem [2]. 4
Exact Algorithm
Before presenting our algorithm, let us formulate the following lemma.
Lemma 3. Let N , J , and L be the instances of Problem 1. Let
be the optimal solution of Problem 2 for each a = 1; : : : ; N
a + L; : : : ; minfN + 1; a + N (J 1)Lg with
(a; b), (a; b)
L + 1, and b =
fi(j) = si(j); j = a; : : : ; b
1; i = 1; : : : ; L ;
where si(j) is the sequence in the input family F of Problem 1, and F (a; b) be
the optimal value of the objective function (
Let ( 1; : : : ; J+1) be the optimal solution of Problem 3 with q(n; m) = F (n; m); n = 1; : : : ; N
L + 1; m = n + L; : : : ; minfN + 1; n + N (J 1)Lg ; (14) in the family Q, and Q be the optimal value of the function (9).
Then the optimal tuples (n1; : : : ; nJL) and ( 1 ; : : : ; L) of Problem 1 can be found by the following formulas: (n(j 1)L+1; : : : ; njL) =
( j ; j+1); j = 1; : : : ; J ; j =
( j ; j+1); j = 1; : : : ; J ;
and the optimal value S of the function (
S = Q : (15) (16) We prove Lemma 3 using the results of Section 3.
Finally, we can present the algorithm for Problem 1.
Algorithm A.
INPUT: a family S of sequences and a positive integer J .
Step 1 (solving the family of Problems 2). For each a = 1; : : : ; N L+1, and
b = a + L; : : : ; minfN + 1; a + N (J 1)Lg, put fi(j) = si(j), j = a; : : : ; b 1,
i = 1; : : : ; L. Using Algorithm A1, nd the optimal solution (a; b), (a; b) and
compute the optimal value F (a; b) of the objective function (
Step 2 (solving Problem 3). Find the family Q in accordance with (14). Find the optimal solution ( 1; : : : ; J+1) and compute the optimal value Q of the objective function (9) using Algorithm A2.
Step 3. Compute the value S of the objective function (
OUTPUT: the tuples (n1; : : : ; nJL), ( 1 ; : : : ; L) and the value S .
The following theorem is true.
Theorem 1. Algorithm A time.
nds an optimal solution of Problem 1 in O(N 5) The optimality of the solution follows from Proposition 1, Proposition 2, and Lemma 3. The total estimate of the running time follows from the inequality LJ N an from the time complexity of the three algorithmic steps. Namely, Step 1, Step 2, and Step 3 require O((N L + 1)2(N (J 1)L)3), O(J N 2), and O(J L) running times respectively.
Remark 1. If J and L are bounded by some constants, then the time complexity of Algorithm A is O(N 5). In a particular case, when L = N we have J = 1 and the running rime the algorithm is O(N 3). 5
Conclusion In the paper we show that one optimization problem arising in applications connected with the analysis of time series is solvable in a polynomial time. In our opinion, the main line of the further research on the problem is to construct faster approximation polynomial-time algorithm with a guaranteed accuracy. In connection with the known Big data problem, a linear-time or a sublinear-time approximation algorithm for the considered problem is of speci c interest. Acknowledgement. The study presented in Sections 3 was supported by the Russian Science Foundation, project 16-11-10041. The study presented in Sections 2, 4 was supported by the Russian Foundation for Basic Research, projects 16-07-00168, and by the Russian Academy of Science (the Program of Basic Research), project 0314-2016-0015, and by the Russian Ministry of Science and Education under the 5-100 Excellence Programme.