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

From MaRDI portal
RedirectionBot (talk | contribs)
Removed claims
Import241208061232 (talk | contribs)
Normalize DOI.
 
(6 intermediate revisions by 6 users not shown)
Property / DOI
 
Property / DOI: 10.2140/moscow.2019.8.357 / rank
Normal rank
 
Property / author
 
Property / author: Iskander M. Aliev / rank
 
Normal rank
Property / reviewed by
 
Property / reviewed by: István Gaál / rank
 
Normal rank
Property / MaRDI profile type
 
Property / MaRDI profile type: MaRDI publication profile / rank
 
Normal rank
Property / OpenAlex ID
 
Property / OpenAlex ID: W3100609971 / rank
 
Normal rank
Property / arXiv ID
 
Property / arXiv ID: 1903.06064 / rank
 
Normal rank
Property / cites work
 
Property / cites work: LLL-reduction for integer knapsacks / rank
 
Normal rank
Property / cites work
 
Property / cites work: On Lovász' lattice reduction and the nearest lattice point problem / rank
 
Normal rank
Property / cites work
 
Property / cites work: On a Problem of Partitions / rank
 
Normal rank
Property / cites work
 
Property / cites work: On a Problem of Partitions II / rank
 
Normal rank
Property / cites work
 
Property / cites work: Gradient elements of the knapsack polytope / rank
 
Normal rank
Property / cites work
 
Property / cites work: An Introduction to the Geometry of Numbers / rank
 
Normal rank
Property / cites work
 
Property / cites work: Some polyhedra related to combinatorial problems / rank
 
Normal rank
Property / cites work
 
Property / cites work: Polynomial Algorithms for Computing the Smith and Hermite Normal Forms of an Integer Matrix / rank
 
Normal rank
Property / cites work
 
Property / cites work: Diophantine approximations and diophantine equations / rank
 
Normal rank
Property / Wikidata QID
 
Property / Wikidata QID: Q127086916 / rank
 
Normal rank
Property / DOI
 
Property / DOI: 10.2140/MOSCOW.2019.8.357 / rank
 
Normal rank

Latest revision as of 01:20, 18 December 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
    0 references
    0 references

    Identifiers

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