Diagonal Frobenius Number via Gomory's Relaxation and Discrepancy

Abstract

For a matrix $A\in Z^{k\times n}$ of rank $k$, the diagonal Frobenius number $F_{\text{diag}}(A)$ is defined as the minimum $t\in Z_{\ge 1}$, such that, for any $b\in {\text{span}}_Z(A)$, the condition \begin{equation*} \exists x \in R_{\geq 0}^n,\, x \geq t \cdot 1 \colon \quad b = A x \end{equation*} implies that \begin{equation*} \exists z \in Z_{\geq 0}^n \colon\quad b = A z. \end{equation*} In this work, we show that \begin{equation*} F_{\text{diag}}(A) = Δ+ O(\log k), \end{equation*} where $\Delta$ denotes the maximum absolute value of $k\times k$ sub-determinants of $A$. From the computational complexity perspective, we show that the integer vector $z$ can be found by a polynomial-time algorithm for some weaker values of $t$ in the described condition. For example, we can choose $t=O(\Delta \cdot \log k)$ or $t=\Delta +O(\sqrt{k}\cdot \log k)$. Additionally, in the assumption that a $2^k$-time preprocessing is allowed or a base $J$ with $|\det A_J|=\Delta$ is given, we can choose $t=\Delta +O(\log k)$. Finally, we define a more general notion of the diagonal Frobenius number for slacks $F_{\text{slack}}(A)$, which is a generalization of $F_{\text{diag}}(A)$ for canonical-form systems, like $Ax\le b$. All the proofs are mainly done with respect to $F_{\text{slack}}(A)$. The proof technique uses some properties of the Gomory's corner polyhedron relaxation and tools from discrepancy theory.