On polynomial-time solvable linear Diophantine problems (Q2332795): Difference between revisions

From MaRDI portal
Added link to MaRDI item.
RedirectionBot (talk | contribs)
Removed claims
Property / author
 
Property / author: Iskander M. Aliev / rank
Normal rank
 
Property / reviewed by
 
Property / reviewed by: István Gaál / rank
Normal rank
 

Revision as of 00:48, 10 February 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

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references