On polynomial-time solvable linear Diophantine problems (Q2332795): Difference between revisions
From MaRDI portal
Set profile property. |
Set OpenAlex properties. |
||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W3100609971 / rank | |||
Normal rank |
Revision as of 20:35, 19 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On polynomial-time solvable linear Diophantine problems |
scientific article |
Statements
On polynomial-time solvable linear Diophantine problems (English)
0 references
5 November 2019
0 references
Let \(A=(B|N)\in \mathbb Z^{m\times n},m\leq n\) with a non-singular part \(B\in \mathbb Z^{m\times m}\) and \(b\in\mathbb Z^m\). The author considers nonnegative integer solutions of the system \(Ax=b\). Denote by \(\ell_N\) the Euclidean length of the longest column in the matrix \(N\). Let \(\mathcal C_B\) be the cone generated by the columns of the matrix \(B\), denote by \(\mathcal C_B(t)\) the affine cone of points in \(\mathcal C_B\) at Euclidean distance \(\ge t\) from the boundary of \(\mathcal C_B\). Denote by \(\gcd(A)\) the greatest common divisor of all \(m\times m\) subdeterminants of \(A\). The author proves that if \[b\in\mathbb Z^m\cap \mathcal C_B\left(\ell_N \left( \frac{|\det(B)|}{\gcd(A)}-1\right)\right)\] then there exists a polynomial-time algorithm which finds a nonnegative integer solution to the system \(Ax=b\) or determines that no such solution exists.
0 references
multidimensional knapsack problem
0 references
polynomial-time algorithms
0 references
asymptotic integer programming
0 references
lattice points
0 references
Frobenius numbers
0 references