Diagonal Frobenius Number via Gomory's Relaxation and Discrepancy
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866915494661980160 |
|---|---|
| author | Gribanov, Dmitry Malyshev, Dmitry Pardalos, Panos |
| author_facet | Gribanov, Dmitry Malyshev, Dmitry Pardalos, Panos |
| contents | 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) = Δ+ O(\log k), \end{equation*} where $Δ$ 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( Δ\cdot \log k)$ or $t = Δ+ 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}}| = Δ$ is given, we can choose $t = Δ+ 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_05629 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Diagonal Frobenius Number via Gomory's Relaxation and Discrepancy Gribanov, Dmitry Malyshev, Dmitry Pardalos, Panos Discrete Mathematics Computational Complexity Computational Geometry Number Theory 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) = Δ+ O(\log k), \end{equation*} where $Δ$ 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( Δ\cdot \log k)$ or $t = Δ+ 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}}| = Δ$ is given, we can choose $t = Δ+ 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. |
| title | Diagonal Frobenius Number via Gomory's Relaxation and Discrepancy |
| topic | Discrete Mathematics Computational Complexity Computational Geometry Number Theory |
| url | https://arxiv.org/abs/2509.05629 |