On polynomial-time solvable linear Diophantine problems
Preprint
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.Keywords
All Related Versions
This publication has 5 references indexed in Scilit:
- LLL-reduction for integer knapsacksJournal of Combinatorial Optimization, 2011
- Gradient elements of the knapsack polytopeCalcolo, 2001
- Polynomial Algorithms for Computing the Smith and Hermite Normal Forms of an Integer MatrixSIAM Journal on Computing, 1979
- Some polyhedra related to combinatorial problemsLinear Algebra and its Applications, 1969
- On a Problem of Partitions IIAmerican Journal of Mathematics, 1954