Convex hulls of superincreasing knapsacks and lexicographic orderings

Research output: Contribution to journalArticlepeer-review

Abstract

We consider bounded integer knapsacks where the weights and variable upper bounds together form a superincreasing sequence. The elements of this superincreasing knapsack are exactly those vectors that are lexicographically smaller than the greedy solution to optimizing over this knapsack. We describe the convex hull of this -dimensional set with O(n) facets. We also establish a distributive property by proving that the convex hull of - and -type superincreasing knapsacks can be obtained by intersecting the convex hulls of - and -sets taken individually. Our proofs generalize existing results for the case.
Original languageEnglish
Pages (from-to)150-163
Number of pages14
JournalDiscrete Applied Mathematics
Volume201
Early online date29 Aug 2015
DOIs
Publication statusPublished - 11 Mar 2016

Fingerprint

Dive into the research topics of 'Convex hulls of superincreasing knapsacks and lexicographic orderings'. Together they form a unique fingerprint.

Cite this