This article is available for purchase or by subscription. See below.
Abstract
|
We obtain a polynomial-time algorithm that, given input
, where
,
, with
nonsingular
and
,
finds a nonnegative integer solution to the system
or determines that no such solution exists, provided that
is located sufficiently “deep” in the cone generated by the columns of
. This
result improves on some of the previously known conditions that guarantee
polynomial-time solvability of linear Diophantine problems.
|
PDF Access Denied
We have not been able to recognize your IP address
34.239.148.127
as that of a subscriber to this journal.
Online access to the content of recent issues is by
subscription, or purchase of single articles.
Please contact your institution's librarian suggesting a subscription, for example by using our
journal-recommendation form.
Or, visit our
subscription page
for instructions on purchasing a subscription.
You may also contact us at
contact@msp.org
or by using our
contact form.
Or, you may purchase this single article for
USD 40.00:
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
|
|