  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
\geq m$. We assume that $a$ is arbitrary, but $b_i = f(i)$, where $f(x) \colon
[0,m) \to \mathbb{R}$ is a function with one of the following properties:
  1. the linear case, when $f(x) =\beta + \alpha \cdot x$;
  2. the monotone case, when $f(i+1) \geq f(i)$, for any $i$;
  3. the convex case, when $f(i+1) - f(i) \geq f(i) - f(i-1)$, for any $i$;
  4. the concave case, when $f(i+1) - f(i) \leq f(i) - f(i-1)$, for any $i$;
  5. the piece-wise linear case, when $f(x)$ consist of $p$ linear pieces;
  6. the polynomial case, when $f \in \mathbb{Z}^d[x]$, for some fixed $d$.
  To the best of our knowledge, the cases 4-6 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.
