Structured \((\min ,+)\)-convolution and its applications for the shortest/closest vector and nonlinear knapsack problems

In this work we consider the problem of computing the \((\min , +)\)-convolution of two sequences a and b of lengths n and m, respectively, where \(n \ge m\). We assume that a is arbitrary, but \(b_i = f(i)\), where \(f(x) :[0,m) \rightarrow {\mathbb {R}}\) is a function with one of the following properties: f is linear, f is monotone, f is convex, f is concave, f is piece-wise linear, f is a polynomial function of a fixed degree. To the best of our knowledge, the concave, piece-wise linear and polynomial cases were not considered in literature before. We develop true sub-quadratic algorithms for them. We apply our results to the knapsack problem with a separable nonlinear objective function, shortest lattice vector, and closest lattice vector problems.

1. Actually, a more general class of rational functions f(x)/g(x), where \(f,g \in {\mathbb {Z}}^d[x]\), could be considered by the cost of using 2d instead of d in the complexity bound. But for the sake of simplicity, this case is not considered. More generally, our approach is applicable to any functions f(x) with a fixed number of inflection points.

Authors and Affiliations

1. National Research University Higher School of Economics, 25/12 Bolshaja Pecherskaja Ulitsa, Nizhny Novgorod, Russian Federation, 603155

   D. V. Gribanov & D. S. Malyshev

2. Lobachevsky State University of Nizhny Novgorod, 23 Gagarina Avenue, Nizhny Novgorod, Russian Federation, 603950

   I. A. Shumilov

Corresponding author

Correspondence to D. V. Gribanov.

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

The article was prepared within the framework of the Basic Research Program at the National Research University Higher School of Economics (HSE). The authors would like to thank A. Vanin and the anonymous reviewers for useful discussions and remarks during preparation of this article.

Appendix

1.1 Proof of Theorem 1

Proof

Description of data structure: Our new data structure is a common segment tree T with some additional augmentations. Here we will use the same notations, as in Sect. 2.2. We augment each vertex v of T with an additional data, represented by a finite set \({\mathscr {G}}_v\) of functions \(g: {\mathcal {D}}_g \cap {\mathbb {Z}}\rightarrow {\mathbb {Z}}\), where each domain \({\mathcal {D}}_g\) is an integer sub-interval of [0, n) and g acts on \({\mathcal {D}}_g\) as a function \(g(x) = A[j] + f(x + t)\), for some \(j,t \in \{{0}, \dots , {n-1}\}\). We will support the following four invariants, for any \(v \in T\):

• Invariant 1: the intervals \({\mathcal {D}}_g\), for any \(g \in {\mathscr {G}}_v\), must split [0, n):

  $$\begin{aligned} {[}0,n) = \bigsqcup \limits _{g \in {\mathscr {G}}_v} {\mathcal {D}}_g; \end{aligned}$$

• Invariant 2: for any \(x \in [0,n)\), there exists a unique function \(g \in {\mathscr {G}}_v\), such that \(x \in {\mathcal {D}}_g\), and

  $$\begin{aligned} {\mathcal {F}}\left( [i_v, j_v); x\right) = g(x); \end{aligned}$$

• Invariant 3: the functions \(g \in {\mathscr {G}}_v\) are stored in the sorted order with respect to the end-points of their domains \({\mathcal {D}}_g\);

• Invariant 4: for any \(g \in {\mathscr {G}}_v\), the function g(x) acts on \({\mathcal {D}}_g\) like \(g(x) = A[j] + f(x + t)\), for \(j,t \in \{{0}, \dots , {n-1}\}\);

Description and analysis of the query operation for basic intervals: For the definition of basic intervals, see Sect. 2.2. Assume that a vertex \(v \in T\) is given, and we want to perform the \(query(i_v, j_v, x)\) operation with respect to the basic interval \([i_v, j_v)\). Due to Invariant 2, we just need to find an appropriate function g from the set \({\mathscr {G}}_v\). Due to Invariant 3, the function g can be found in \(O(\log (n))\) time, because \({\mathscr {G}}_v\) contains at most n functions. Due to Invariant 4, g(x) looks like \(A[j] + f(x + t)\), so it can be computed, using a single call to \(E\!V\). The total complexity is \(O(\log _2(n))\).

Description and analysis of the query operation for general intervals: Assume that an interval [i, j) is given, and we want to perform the query(i, j, x) operation. Due to Lemma 1, there exist \(m \le 2 \log _2(n)\) vertices \(v_1, v_2, \dots , v_m \in T\), such that [i, j) is partitioned into the basic intervals \([i_{v_k}, j_{v_k})\), for \(k \in \{{1}, \dots , {m}\}\). Let us assume that \(i_{v_1}< i_{v_2}< \dots < i_{v_m}\), and let \(h_k = i_{v_k} - i_{v_1}\). Due to the property (1), we have

Consequently, due to the complexity bound on queries for basic intervals, the complexity of the query(i, j, x) operation is \(O(\log ^2(n))\).

Description and analysis of the preprocessing:

First of all, let us construct the standard segment tree T, described in Sect. 2.2, for the array A. It will take O(n) time and space. We need to show how to compute \({\mathscr {G}}_v\), for any \(v \in T\), and satisfy all the invariants. The algorithm is recursive: it starts from the leafs, and moves upper, until it meats the root of T. Let v be a leaf. Since \(j_v - i_v = 1\), \({\mathcal {F}}\left( [i_v,j_v); x\right) = A[i_v] + f(x)\). Consequently, \({\mathscr {G}}_v\) consists of only one function \(g(x) = A[i_v] + f(x)\), and \({\mathcal {D}}_g = [0, n)\).

Next, we assume that v is not a leaf, and let u and w be the children of v. We will show how the set \({\mathscr {G}}_v\) can be constructed from the sets \({\mathscr {G}}_u\) and \({\mathscr {G}}_w\), based on the formula

which is a direct application of (1). Let \({\mathcal {P}}_u\) and \({\mathcal {P}}_w\) be the sets of end-points of intervals, representing the domains of functions inside \({\mathscr {G}}_u\) and \({\mathscr {G}}_w\). We assume that \(0, n \in {\mathcal {P}}_u\) and \(0, n \in {\mathcal {P}}_w\). Clearly, \(\left| {{\mathcal {P}}_u}\right| =\left| {{\mathscr {G}}_u}\right| + 1\) and \(\left| {{\mathcal {P}}_w}\right| = \left| {{\mathscr {G}}_w}\right| + 1\). Due to Invarinat 3, we can assume that \({\mathcal {P}}_u\) and \({\mathcal {P}}_w\) are sorted. Next, we merge \({\mathcal {P}}_u\) and \({\mathcal {P}}_w\) into \({\mathcal {P}}_v\), maintaining the same sorting order, and remove the duplicates. The last step can be done in \(O(\left| {{\mathscr {G}}_u}\right| + \left| {{\mathscr {G}}_w}\right| )\)-time, since \({\mathcal {P}}_u\) and \({\mathcal {P}}_w\) are sorted. Since the points 0, n are common for both \({\mathcal {P}}_u\) and \({\mathcal {P}}_v\), we have

Take a pair \(\nu , \tau \) of consecutive points in \({\mathcal {P}}_v\). Due to Invariant 2, there exist unique functions \(g_u \in {\mathscr {G}}_u\) and \(g_w \in {\mathscr {G}}_w\), such that \([\nu , \tau ) \subseteq {\mathcal {D}}_{g_u} \cap {\mathcal {D}}_{g_w}\). Due to the formula (19), for \(x \in [\nu , \tau )\), we have

Let \(h(x) = g_u(x) - g_w(x + j_u - i_u)\), defined on \([\nu , \tau )\). Due to Invariant 4, the function h(x) has the form \(f(x+a) - f(x+b) + c\), for some \(a,b \in {\mathbb {Z}}_{\ge 0}\) and \(c \in {\mathbb {Z}}\).

To efficiently precompute \({\mathcal {F}}\left( [i_v,j_v); x\right) \) for \(x \in [\nu , \tau ) \cap {\mathbb {Z}}\), we need to compute a minimal sign partition \({\mathcal {S}}\in {\mathscr {P}}(h, [\nu , \tau ))\). It can be done by a single call to \(S\!P\). Now, for any interval \({\mathcal {I}}\in {\mathcal {S}}\), if \(h(x) \ge 0\) on \({\mathcal {I}}\), then \({\mathcal {F}}\left( [i_v,j_v); x\right) = g_u(x)\) and \({\mathcal {F}}\left( [i_v,j_v); x\right) = g_w(x + j_u - i_u)\) in the opposite case \(h(x) \le 0\). Consequently, for any such interval \({\mathcal {I}}\), we create a new function \(g_{{\mathcal {I}}}\) and put it inside \({\mathscr {G}}_v\) in the sorted order with respect to endpoints of \({\mathcal {I}}\). Hence, the interval \([\nu , \tau )\) will be decomposed into at most p new sub-intervals, and the same number of new functions will be added into \({\mathscr {G}}_v\).

Now, let us estimate the time and space requirements to build the set \({\mathscr {G}}_v\). As it was shown before, for any pair \([\nu ,\tau )\) of consecutive points from \({\mathcal {P}}_v\), we add at most p functions to \({\mathscr {G}}_v\). Therefore, due to (20), we have

Denote \(N(m) = \max \left\{ \left| {{\mathscr {G}}_v}\right| :v \in T,\; j_v - i_v =m \right\} \), for \(m \le n\) being a power of 2. Since \(N(1) = 1\), we have

And, since we always work in the interval [0, n),

By analogy with N(m), let us denote the maximal time to construct \({\mathscr {G}}_v\) (in the assumption that \({\mathscr {G}}_u\) and \({\mathscr {G}}_w\) are already constructed) by \(t_{node}(m)\), where \(m = j_v - i_v\). By the word "time", we mean both arithmetical and oracle complexities. Clearly, the definition is correct, because the value of m is the same for all the vertices of the same level in T. Since the complexity to compute \({\mathscr {G}}_v\) is linear with respect to the resulting size of \({\mathscr {G}}_v\), due to (21),

Note additionally that the space requirements to store \({\mathscr {G}}_v\) with the whole information, related to v, can be described by the same function \(t_{node}(m)\). Now, let us compute the total time and space complexity to construct the final augmented tree T. It can be expressed by the function

Let \(s = \left\lceil \log _2\left( n^{\frac{1}{1+\log _2 (p)}} \right) \right\rceil \). To calculate the asymptotic of t(n), we split the sum into two parts and estimate elements of each sum, using (22):

Estimating the sum at the end of the last formula, we have:

Finally, the total time and space requirements can be estimated as follows

\(\square \)

1.2 Proof of Lemma 2

Proof

Put \({\mathcal {I}}= \{{0}, \dots , {n-1}\}\). To prove the lemma, we will use the criteria, given in [50, Corollary 1]. For given \(g_0, g_1, \dots , g_{n-1}\), it states that the \(C^{1,L}\)-smooth convex function f with \(f'(x_i) = g_i\) exists if and only if the following conditions are satisfied:

We construct \(g_i\) in the following way. We choose \(g_0 < d_1\) and \(g_{n-1} > d_{n-1}\). For \(i \in \{{1}, \dots , {n-2}\}\), if \(d_{i} < d_{i+1}\), we choose \(g_i\) strictly between \(d_{i}\) and \(d_{i+1}\): \(d_{i}< g_i < d_{i+1}\). In the opposite case, when \(d_{i} = d_{i+1}\), we just set \(g_i:= d_i\).

Fix \(i,j \in \{{1}, \dots , {n-2}\}\). Assume firstly that \(d_{k} = d_{l}\), for all k, l between (inclusively) i, j. Then, the following equality, for any \(\varepsilon > 0\), holds, which follows from the definition of \(d_i\):

Now, assume that \(d_k \not = d_{k+1}\), for some k between (inclusively) i, j. Then, since \(g_k > d_k\), we have

for any sufficiently small \(\varepsilon > 0\). Finally, if \(i = 0\) or \(j = n-1\), the same inequality holds, because \(g_0 < d_1\) and \(g_{n-1} > d_{n-1}\).

Therefore, since \({\mathcal {I}}\) is finite, we can choose \(\varepsilon \) sufficiently small, such that the following inequality will hold, for any \(i,j \in {\mathcal {I}}\):

\(\square \)

1.3 Proof of Lemma 3

Proof

Assume that f is convex. In the opposite case, we can consider a function \(-g(x) = \left( -f(x+a)\right) - b -\left( -f(x)\right) \). Clearly, all the sign partitions of g(x) and \(-g(x)\) are equivalent. Next, we can assume that f is \(C^1\)-smooth. Definitely, if f is not \(C^1\)-smooth, due to Lemma 2, there exists a convex \(C^1\)-smooth function h, such that \(h(x) = f(x)\), for all \(x \in [\alpha ,\beta ) \cap {\mathbb {Z}}\). Since any minimal sign partition of f consists of intervals with integer end-points, the sign partitions for h and f are equivalent, and we can use h instead of f.

Additionally, we assume that \(a > 0\), because, in the opposite case, both statements are trivial. Now, we claim that the equality \(g(x) =0\) is possible only for points in some connected interval \([\nu , \tau ] \subseteq [\alpha ,\beta )\). Assume that \(g(\nu ) = 0\) and \(g(\tau ) = 0\), for some \(\nu ,\tau \in [\alpha ,\beta )\) with \(\tau > \nu \). By definition, we have

Due to \(C^1\)-smoothness of f, we can use the fundamental theorem of calculus:

Put \(\delta = \tau - \nu \). Make a change of variables \(x \rightarrow x - \delta \) and \(x \rightarrow x + \delta \) in (24):

Combining (24) and (25), we get

Since f is convex, \(f'(x+\delta ) - f'(x) \ge 0\) and \(f'(x) - f'(x-\delta ) \ge 0\), and, consequently,

Again, since \(f'(x)\) is convex, \(f'(x) = {{\,\textrm{const}\,}}\), for the whole interval \([\nu , \tau ]\). Consequently, \(g'(x) = 0\) and \(g(x) = {{\,\textrm{const}\,}}\), for \(x \in [\nu , \tau ]\). Since \(g(\nu ) = 0\), it holds that \(g(x) = 0\), for \(x \in [\nu , \tau ]\). So, the claim is proved.

Therefore, any given interval \({\mathcal {I}}\subseteq [\alpha ,\beta )\), where g is well-defined, can be partitioned into at most three parts: strict inequalities \(g(x) > 0\) or \(g(x) < 0\) on the left and right sides, and equality \(g(x) = 0\) in the middle. Consequently, any minimal sign partition of g on \({\mathcal {I}}\) consists of at most 2 pieces, which proves the inequality \(p_f \le 2\). To calculate such a partition, we need to find an integer point \(z \in {\mathcal {I}}\) with \(g(z) = 0\). Or, in the case, when \(g(x) \not = 0\) for all \(x \in {\mathcal {I}}\cap {\mathbb {Z}}\), we need to calculate a point z, such that \(g(z) < 0\) and \(g(z+1) > 0\), or vice-versa. Clearly, in both cases we can use the standard dichotomy principle that takes \(O( \log (n) )\) calls to \(E\!V\). \(\square \)

1.4 Proof of Lemma 4

Proof

First we need to prove the following auxiliary lemma:

Lemma 5

Let \(g_1 = g_2 = \dots = g_k\), for \(k \in \{{1}, \dots , {n}\}\), and \(x^*\) be an optimal solution of 17. Denote \(S = x_1^* + \dots + x_k^*\). Then, there exists an optimal solution \(z^*\) with the following structure:

1. (i)

   If \(S \ge 0\), then:

   $$\begin{aligned} z^* = (a+1, a+1, \dots , a+1, a , a, \dots , a)^\top , \quad \text {where}\ a \in {\mathbb {Z}}_{\ge 0}. \end{aligned}$$

   (26)
2. (ii)

   If \(S < 0\), then:

   $$\begin{aligned} z^* = -(a, a, \dots , a, a+1 , a+1, \dots , a+1)^\top , \quad \text {where}\ a \in {\mathbb {Z}}_{\ge 0}. \end{aligned}$$

   (27)

Proof

Note that the expressions \(g_1 \cdot x_1^* + \dots + g_k \cdot x_k^*\) and \(g_1 \cdot S\) are equivalent in therms of constraints of (17). Assume that \(S \ge 0\). First of all, we claim that there exists an optimal solution \(z^*\) with the property \(z^*_i \ge 0\), for \(i \in \{{1}, \dots , {k}\}\). Assume that there exist \(i,j \in \{{1}, \dots , {k}\}\) with \(x^*_i \ge 1\) and \(x^*_j \le -1\). Since \(S \ge 0\), if \(x^*_j\) exists, then \(x^*_i\) exists also. Next, we construct a vector \(z^*\), which coincides with \(x^*\) in all the coordinates, except i, j. Put \(z^*_i = x^*_i - 1\) and \(z^*_j =x^*_j + 1\). Due to Property 1, we have \(\sum _{i=1}^k f_i(z^*_i) \le \sum _{i=1}^k f_i(x^*_i)\). Such a procedure can be repeated until no negative coordinates remain. Consequently, it can be assumed that \(x^*_i \ge 0\), for \(i \in \{{1}, \dots , {k}\}\). Let us consider the following auxiliary optimization problem:

Clearly, \(x^*[1,k]\) gives an optimal solution of this problem, and vice versa, an optimal solution of 6.4 could be used to generate the first k coordinates of \(x^*\). Let us consider the set \({\mathcal {S}}= \{x \in {\mathbb {Z}}^k_{\ge 0} :x_1 + \dots +x_k \le S\}\). Elements of \({\mathcal {S}}\) could be treated as the characteristic vectors of multisets with the cardinality S. Identifying vectors with multisets, we can see that \({\mathcal {S}}\) is a matroid, see, for example, [33, Proposition 13.4, Part 13. Matroids]. The vectors \(z \in {\mathcal {S}}\) with \(z_1 + \dots + z_k = S\) are the bases of \({\mathcal {S}}\). Consequently, an optimal solution of 6.4 is exactly a base of \({\mathcal {S}}\) with the minimal possible value of the objective function. Since \({\mathcal {S}}\) is a matroid, an optimal solution of 6.4 can by found by the following greedy algorithm:

1. 1.

   Assign \(s:= 0\), \(x:= \textbf{0}^k\), and \(F: = f_1(0) + \dots + f_k(0)\);

2. 2.

   While \(s \le S\) do the following:

3. 3.

         Choose \(i \in \{{1}, \dots , {k}\}\), such that the value \(f_i(x_i+1) - f_i(x_i)\) is minimal;

4. 4.

         Assign \(x_i:= x_i + 1\), \(s:= s+1\), and \(F:= F + f_i(x_i+1) - f_i(x_i)\);

5. 5.

         Move to the step 2;

6. 6.

   Return x as a greedy solution and F as f(x);

Due to the properties 4,5, there exists a greedy solution \(z^*\) that looks like (26). This proves the lemma for the case \(S \ge 0\). The case \(S < 0\) is absolutely similar. \(\square \)

If \(x^*\) is an optimal solution of (17), then, due to Lemma 5, there exists an optimal solution \(z^*\) of (17), such that the first k components of \(z^*\) look like (26) or (27). By the definition of h, we have \(\sum _{i=1}^k f_i(z^*_i) = h(y)\), where \(y = z_1^* + \dots z_k^*\). Note that \((y,\, x^*[k+1,n])\) is a feasible solution of (18) with the same value of the objective function. In the opposite direction, let \((y,\, x^*)\) be an optimal solution of (18). Let us construct the vector z as it was described in the lemma definition. Clearly, the vector \(\left( {\begin{array}{c}z\\ x^*\end{array}}\right) \) is a feasible solution of (17) with the same value of the objective function.

Finally, let us explain how to compute \(h(0),h(1), \dots , h(m)\) with O(m) operations. Assume that h(i) has already been computed, and let \(r = i \bmod k\) and \(a = \lfloor i / k \rfloor \). Then, by the definition of h, we have \(h(i + 1) = h(i) + f_{r+1}(a+1) - f_{r+1}(a)\). Hence, we need O(1) operations to compute \(h(i+1)\) and O(m) operations to compute the whole sequence. A similar algorithm works for \(h(0), h(-1), \dots , h(-m)\). The proof of Lemma 4 is finished. \(\square \)

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions