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

Optimization Letters. 2024. Vol. 18. P. 73–103.

D. V. Gribanov, Shumilov I. A., D. S. Malyshev

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≥m. We assume that a is arbitrary, but b_i=f(i), where f(x):[0,m)→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.

Keywords: dynamic programming, convolution, nonlinear knapsack, separable objective, shortest vector problem, closest vector problem, integer programming ·, piece-wise linear

Publication based on the results of: Research on graph and network structures and its applications (2023)