The vertices of the knapsack polytope

DOI10.1016/0166-218X(83)90067-7zbMath0523.90063OpenAlexW2083839413MaRDI QIDQ1056676

A. C. Hayes, David G. Larman

Publication date: 1983

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0166-218x(83)90067-7

zbMATH Keywords

algorithmcombinatorial optimizationknapsack problemknapsack polytopesmallest number of vertices

Mathematics Subject Classification ID

Integer programming (90C10) Polytopes and polyhedra (52Bxx)

Related Items

Knapsack polytopes: a survey, New Algorithmic Results for Bin Packing and Scheduling, Convex digital polygons, maximal digital straight segments and convergence of discrete geometric estimators, On the number of irreducible points in polyhedra, Computing convex hulls and counting integer points with \texttt{polymake}, Upper and lower bound results on the convex hull of integer points in polyhedra, On \(\Delta\)-modular integer linear problems in the canonical form and equivalent problems, On integer points in polyhedra, On the polyhedral complexity of the integer points in a hyperball, On integer points in polyhedra: A lower bound, Carathéodory bounds for integer cones, Some theoretical challenges in digital geometry: a perspective, Approximation of convex sets by polytopes, About the Structure of the Integer Cone and Its Application to Bin Packing, Computing the integer hull of convex polyhedral sets

Cites Work

• Unnamed Item
• On the upper-bound conjecture for convex polytopes
• Integer Programming with a Fixed Number of Variables
• Khachiyan’s algorithm for linear programming