| Abstrakt: |
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. [ABSTRACT FROM AUTHOR] |
Full text from SpringerLink