Polynomial algorithms for \(m\times (m+1)\) integer programs and \(m\times (m+k)\) diophantine systems (Q2265948)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 3892939
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Polynomial algorithms for \(m\times (m+1)\) integer programs and \(m\times (m+k)\) diophantine systems |
scientific article; zbMATH DE number 3892939 |
Statements
Polynomial algorithms for \(m\times (m+1)\) integer programs and \(m\times (m+k)\) diophantine systems (English)
0 references
1985
0 references
Recent results \textit{R. Kannan} and \textit{A. Bachem} [SIAM J. Comput. 8, 499-507 (1979; Zbl 0446.65015)] (on computing the Smith Normal Form of a matrix) and \textit{H. W. Lenstra} [Math. Oper. Res. 8, 538-548 (1983; Zbl 0524.90067)] (on solving integer inequality systems) are used with classical results by H. J. S. Smith (1861) to obtain polynomial-time algorithms for solving \(m\times (m+1)\) equality constrained integer programs and \(m\times (m+k)\) systems of diophantine equations for fixed k.
0 references
computational complexity
0 references
polynomial-time algorithms
0 references
equality constrained integer programs
0 references
diophantine equations
0 references
0 references
0.8948108
0 references
0 references
0.87977105
0 references
0.8768109
0 references
0.8728346
0 references
0.8716378
0 references
0 references
