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_{ \geq 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) = \Delta + 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 $A x \leq 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.
Categories: cs.DM cs.CC cs.CG math.NT