paper

Simpler Algorithms for Knapsack, Subset Sum, and Min-Plus Convolution

arXiv:2609.37449

Abstract

We simplify algorithms for Knapsack, output-sensitive Subset Sum, and near-convex min-plus convolution. For bounded Knapsack, we give a deterministic algorithm using arithmetic and comparison operations, where is the maximum item weight and counts input records with binary-encoded multiplicities. Following Bringmann's approach, we partition the items and bound the weight added or removed within each part when correcting a greedy solution to an optimum. These bounds keep the dynamic-programming tables small. The same analysis gives the corresponding bound with maximum profit in place of weight. For multiple-choice Knapsack, we give a randomized algorithm, where counts alternatives, counts classes, and is the maximum within-class weight range. Randomly grouping classes exploits cancellation between positive and negative weight changes. For Subset Sum of nonnegative integer vectors in any fixed dimension , we obtain expected time , where counts attainable sums in the target box. With high probability, all sums are returned within the same bound. This improves the bound of Bringmann, Fischer, and Nakos for . The key step computes a sumset inside a box without generating the potentially much larger unrestricted sumset. Finally, we simplify the algorithm for min-plus convolution of integer arrays of total length , where is the sum of their maximum deviations above convex arrays. The deviations can change the minimizing pairs substantially, but restrict relevant candidate values to short intervals.