Feasibility of integer knapsacks

DOI10.1137/090778043MaRDI QIDQ3083317zbMATH OpenOpenAlexFDO

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, http://orca.cf.ac.uk/24988/1/Aliev%202010.pdf

zbMATH Keywords

distribution of latticesFrobenius numbersinhomogeneous minimumknapsack problemsuccessive minima

Mathematics Subject Classification ID

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

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

(16)

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

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)