Diagonal Frobenius Number via Gomory's Relaxation and Discrepancy

For a matrix A ∈ Zk × n of rank k, the diagonal Frobenius number Fdiag(A) is defined as the minimum t ∈ Z≥ 1, such that, for any b ∈ spanZ(A), the condition {equation*} ∃ x ∈ R≥ 0^n,\, x ≥ t · 1 b = A x {equation*} implies that {equation*} ∃ z ∈ Z≥ 0^n b = A z. {equation*} In this work, we show that {equation*} Fdiag(A) = Δ+ O(log k), {equation*} where $Δ$ denotes the maximum absolute value of k × 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( Δ· log k) or t = Δ+ O(√k · log k). Additionally, in the assumption that a 2ᵏ-time preprocessing is allowed or a base J with | AJ| = Δ is given, we can choose t = Δ+ O(log k). Finally, we define a more general notion of the diagonal Frobenius number for slacks Fslack(A), which is a generalization of Fdiag(A) for canonical-form systems, like A x ≤ b. All the proofs are mainly done with respect to Fslack(A). The proof technique uses some properties of the Gomory's corner polyhedron relaxation and tools from discrepancy theory.