Faster 0-1-Knapsack via Near-Convex Min-Plus-Convolution.

Karl Bringmann Alejandro Cassis

Published in: ESA (2023)

Keyphrases

knapsack problem
dynamic programming
image processing
piecewise linear
convex hull
convex optimization
optimal solution
memory efficient
upper bound
feasible solution
convexity properties
convex functions
convex sets
globally optimal
special case
multiresolution
bayesian networks