On polynomial-time solvable linear Diophantine problems

DOI10.2140/MOSCOW.2019.8.357MaRDI QIDQ2332795zbMATH OpenOpenAlexWikidataFDO

Authors Iskander Aliev

Publication date 5 November 2019

Published in Moscow Journal of Combinatorics and Number Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1903.06064, http://orca.cf.ac.uk/124630/1/PolySubcone0107.pdf

zbMATH Keywords

asymptotic integer programmingFrobenius numberslattice pointsmultidimensional knapsack problempolynomial-time algorithms

Mathematics Subject Classification ID

Linear Diophantine equations (11D04) The Frobenius problem (11D07) Lattices and convex bodies (number-theoretic aspects) (11H06) Computer solution of Diophantine equations (11Y50) Integer programming (90C10)

Abstract: We obtain a polynomial-time algorithm that, given input (A, b), where A=(B|N) is an integer mxn matrix, m<n, with nonsingular mxm submatrix B and b is an m-dimensional integer vector, finds a nonnegative integer solution to the system Ax=b or determines that no such solution exists, provided that b is located sufficiently "deep" in the cone generated by the columns of B. This result improves on some of the previously known conditions that guarantee polynomial-time solvability of linear Diophantine problems.

Review text

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.

Recommendations

• scientific article; zbMATH DE number 4077322
• scientific article; zbMATH DE number 1090094
• Polynomial algorithms for m (m+1) integer programs and m (m+k) diophantine systems
• A fast method for finding the basis of non-negative solutions to a linear diophantine equation
• scientific article; zbMATH DE number 1684382

Cites work

• An Introduction to the Geometry of Numbers
• Diophantine approximations and diophantine equations
• Gradient elements of the knapsack polytope
• LLL-reduction for integer knapsacks
• On a Problem of Partitions
• On a Problem of Partitions II
• On Lovász' lattice reduction and the nearest lattice point problem
• Polynomial Algorithms for Computing the Smith and Hermite Normal Forms of an Integer Matrix
• Some polyhedra related to combinatorial problems

Cited in

(7)

• Finding a partial solution to a linear system of equations in positive integers
• Polyhedral omega: a new algorithm for solving linear Diophantine systems
• Lower bounds for solving linear diophantine equations on random access machines
• scientific article; zbMATH DE number 4077322 (Why is no real title available?)
• On The Number of Nonnegative Integer Solutions of a System of Linear Diophantine Equations
• scientific article; zbMATH DE number 1405441 (Why is no real title available?)
• The complexity of almost linear diophantine problems

This page was built for publication: On polynomial-time solvable linear Diophantine problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2332795)