Vol. 8, No. 4, 2019

Download this article
Download this article For screen
For printing
Recent Issues
Volume 8, Issue 4
Volume 8, Issue 3
Volume 8, Issue 2
Volume 8, Issue 1
The Journal
About the Journal
Editorial Board
Subscriptions
Submission Guidelines
Submission Form
Ethics Statement
Editorial Login
ISSN (electronic): 2640-7361
ISSN (print): 2220-5438
Previously Published
To Appear
founded and published with the
scientific support and advice of the
Moscow Institute of
Physics and Technology
 
Other MSP Journals
On polynomial-time solvable linear Diophantine problems

Iskander Aliev

Vol. 8 (2019), No. 4, 357–365
Abstract

We obtain a polynomial-time algorithm that, given input (A,b), where A = (B|N) m×n , m < n, with nonsingular B m×m and b m , 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
multidimensional knapsack problem, polynomial-time algorithms, asymptotic integer programming, lattice points, Frobenius numbers
Mathematical Subject Classification 2010
Primary: 11D04, 90C10
Secondary: 11H06
Milestones
Received: 15 March 2019
Revised: 1 July 2019
Accepted: 15 July 2019
Published: 11 October 2019
Authors
Iskander Aliev
Mathematics Institute
Cardiff University
Cardiff
United Kingdom