Feasibility of integer knapsacks

DOI10.1137/090778043MaRDI QIDQ3083317zbMATHOpenAlexFDO

Authors Martin Henk, Iskander Aliev

Publication date 21 March 2011

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

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

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)

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.

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; zbMATH DE number 18540
• scientific article; zbMATH DE number 3910473

Cited in

(15)

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

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)