Feasibility of integer knapsacks

DOI10.1137/090778043zbMATH Open1211.90132arXiv0911.4186OpenAlexW2069926530MaRDI QIDQ3083317FDOQ3083317

Iskander Aliev, Martin Henk

Publication date: 21 March 2011

Published in: SIAM Journal on Optimization (Search for Journal in Brave)

Abstract: 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.

Full work available at URL: https://arxiv.org/abs/0911.4186

Recommendations

• Integer points in knapsack polytopes and \(s\)-covering radius
• Integer knapsacks: average behavior of the Frobenius numbers
• Hard Equality Constrained Integer Knapsacks
• scientific article
• scientific article; zbMATH DE number 3910473

zbMATH Keywords

knapsack problemsuccessive minimaFrobenius numbersinhomogeneous minimumdistribution of lattices

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Integer programming (90C10) Lattices and convex bodies (number-theoretic aspects) (11H06) The Frobenius problem (11D07)

Cited In (13)

• Bounds on generalized Frobenius numbers
• Computing Optimized Path Integrals for Knapsack Feasibility
• A Polyhedral Frobenius Theorem with Applications to Integer Optimization
• Integer knapsack problems with profit functions of the same value range
• On the lattice programming gap of the group problems
• LLL-reduction for integer knapsacks
• Hard Equality Constrained Integer Knapsacks
• Homeomorphic measures on stationary Bratteli diagrams
• Integer points in knapsack polytopes and \(s\)-covering radius
• Proximity bounds for random integer programs
• Proximity bounds for random integer programs
• The Frobenius problem over number fields with a real embedding
• Positive semigroups and generalized Frobenius numbers over totally real number fields

This page was built for publication: Feasibility of integer knapsacks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3083317)