论文标题
结构化$（\ min，+）$ - 卷积及其在最短矢量，最接近的向量和可分离的非线性背包问题的应用
Structured $(\min,+)$-Convolution And Its Applications For The Shortest Vector, Closest Vector, and Separable Nonlinear Knapsack Problems
论文作者
论文摘要
在这项工作中，我们考虑了计算$（\ min， +）$ - 分别为$ a $ a $和$ b $的$ n $和$ n $和$ m $的卷积的问题，其中$ n \ geq m $。我们假设$ a $是任意的，但是$ b_i = f（i）$，其中$ f（x）\ colon [0，m）\ to \ mathbb {r} $是具有以下属性之一的函数： 1。线性情况，当$ f（x）=β+α\ cdot x $时； 2。单调案例，当$ f（i+1）\ geq f（i）$时，对于任何$ i $; 3。凸情况，当$ f（i+1）-f（i）\ geq f（i）-f（i -1）$，对于任何$ i $; 4。凹面案例，当$ f（i+1）-f（i）\ leq f（i）-f（i -1）$，对于任何$ i $; 5。零件线性盒，当$ f（x）$由$ p $线性零件组成时； 6。对于某些固定的$ d $，当$ f \ in \ mathbb {z}^d [x] $中时，多项式情况。 据我们所知，案件4-6以前没有考虑过。我们为它们开发了真正的次级算法。 我们将结果应用于背包问题，具有可分离的非线性目标函数，最短的晶格向量和最接近的晶格向量问题。
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) =β+ α\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.
