Knapsack polytopes: a survey
Lists
Only you see this
Abstract
The 0/1 knapsack polytope is the convex hull of all 0/1 vectors that satisfy a given single linear inequality with non-negative coefficients. This paper provides a comprehensive overview of knapsack polytopes. We discuss basic polyhedral properties, (lifted) cover and other valid inequalities, cases for which complete linear descriptions are known, geometric properties for small dimensions, and connections to independence systems. We also discuss the generalization to (mixed-)integer knapsack polytopes and variants.
BibTeX
@article{hojny2020knapsack,
author = {Christopher Hojny and Tristan Gally and Oliver Habeck and Hendrik Lüthen and Frederic Matter and Marc E. Pfetsch and Andreas Schmitt},
title = {{Knapsack polytopes: a survey}},
journal = {Ann. Oper. Res.},
year = {2020},
doi = {10.1007/s10479-019-03380-2},
}Loading related content...