D. V. Gribanov

collaborators

2 papers

cs.CC2022

Structured $(min, +)$ -Convolution And Its Applications For The Shortest Vector, Closest Vector, and Separable Nonlinear Knapsack Problems

D. V. Gribanov, I. A. Shumilov, 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 \geq m$ . We assume that $a…

cs.DM2022

On a Simple Connection Between $Δ$ -modular ILP and LP, and a New Bound on the Number of Integer Vertices

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

Let $A \in Z^{m \times n}$ , $r ank (A) = n$ , $b \in Z^{m}$ , and $P$ be an $n$ -dimensional polyhedron, induced by the system $A x \leq b$ . It is a known fact that if $F$ is a $k$ -face o…

Structured (min,+)-Convolution And Its Applications For The Shortest Vector, Closest Vector, and Separable Nonlinear Knapsack Problems

On a Simple Connection Between Δ-modular ILP and LP, and a New Bound on the Number of Integer Vertices

Structured $(min, +)$ -Convolution And Its Applications For The Shortest Vector, Closest Vector, and Separable Nonlinear Knapsack Problems

On a Simple Connection Between $Δ$ -modular ILP and LP, and a New Bound on the Number of Integer Vertices