Diagonal Frobenius Number via Gomory Relaxation and Discrepancy

In this work, we consider an ILP problem of the form: find a non-negative integer vector $(x)$ satisfying the system $(A x = b)$ with given integer inputs $(A, b)$. The following fact is known: if the system $(A x = b)$ has a non-negative real solution $x$ whose components are all sufficiently large, then the system also has a non-negative integer solution $(z)$. The minimal required magnitude of the components of $(x)$ is called the diagonal Frobenius number of the matrix $(A)$ and represents a natural generalization of the classical Frobenius number. Moreover, under stronger conditions on the magnitude of the components of $(x)$, the corresponding solution $(z)$ can be found by a polynomial-time algorithm. As our main result, we present new bounds on the diagonal Frobenius number, which significantly improve all previously known bounds, including those for the polynomially solvable case.
This is a joint work with Nikita Kasyanov, LATNA & HSE University.