On Feasibility of Integer Knapsacks

Details On Feasibility of Integer Knapsacks On Feasibility of Integer Knapsacks

2009-11-21

arxiv.org/abs/0911.4186v1

Mathematics

Optimization and Control

Scientific paper

Given an integer mxn matrix A satisfying certain regularity assumptions, we consider the set F(A) of all integer vectors b such that the associated knapsack polytope P(A,b)={x: Ax=b, x>=0} contains an integer point. When m=1 the set F(A) is known to contain all consecutive integers greater than the Frobenius number associated with A. In this paper we introduce the diagonal Frobenius number g(A) which reflects in an analogous way feasibility properties of the problem and the structure of F(A) in the general case. We give an optimal upper bound for g(A) and also estimate the asymptotic growth of the diagonal Frobenius number on average.

Affiliated with

Also associated with

No associations

Rating

On Feasibility of Integer Knapsacks does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On Feasibility of Integer Knapsacks, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On Feasibility of Integer Knapsacks will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-316239