Introduction
The Unbounded SubsetSum problem is a cornerstone of combinatorial optimization and theoretical computer science. In its simplest form, the problem asks whether a target value $t$ can be formed by summing elements from a set of weights $W$, where each weight can be used an unlimited number of times. While textbook dynamic programming solutions have existed for decades, achieving optimal efficiency for its more complex variants—specifically "All-Target" generalizations—has remained a significant challenge.
This paper introduces a unified combinatorial framework that achieves near-linear time complexity for several of these variations, including the All-Target CoinChange and Residue Table problems. By exploiting the structural properties of lexicographically smallest optimal solutions, the authors bridge the gap between theoretical complexity and practical algorithmic efficiency.
Problem Definitions
The research focuses on three primary generalizations of the Unbounded SubsetSum problem:
- All-Target CoinChange: Given a set of coin denominations, find the minimum number of coins required to reach every integer $c$ up to a limit $t$.
- All-Target Unbounded Knapsack: Given weights with associated profits, determine the maximum profit achievable for every total weight $c \in [0, t]$.
- Residue Table: For a set of weights, find the smallest possible sum that leaves a specific remainder when divided by the smallest weight $w_1$. This is a fundamental component in solving the Frobenius (Coin) Problem.
Historically, algorithms for these problems were constrained by complexities such as $O(t^{4/3})$ or $O(t^{3/2})$. This work aims for "near-linear" time, denoted as $\tilde{O}(u + t)$, where $u$ represents the maximum weight and $t$ the target range.
A Unified Combinatorial Framework
The core innovation of this paper is a two-phase approach centered on the concept of Witness Propagation and lexicographical ordering.
Lexicographical Ordering and the Kernel Concept
To manage the vast search space of potential solutions, the authors impose an arbitrary order on the items. They focus exclusively on the "lexicographically smallest" optimal solutions. This constraint reveals a critical structural property: any optimal solution can be reduced to a small "core" or kernel. The authors prove that these kernels only require a logarithmic number of item types ($O(\log u)$), drastically simplifying the underlying combinatorial structure.
Phase 1: Kernel Computation
The algorithm first computes optimal solutions for these small kernels. This is achieved using specialized convolution techniques—specifically boolean or (min, +) convolutions—to identify "minimum witnesses." A witness is the specific item that contributes to the lexicographically smallest solution for a given target.
Phase 2: Witness Propagation
Leveraging the optimal substructure property, the algorithm propagates the kernel solutions forward. Because removing one item from an optimal solution (under lexical order) leaves an optimal solution for the remaining value, the full table of results can be constructed iteratively in near-linear time.
Key Theoretical Results
The paper establishes new state-of-the-art complexity bounds for these fundamental problems:
- All-Target CoinChange: The authors achieve a complexity of $\tilde{O}(u + t)$, a significant leap from previous sub-linear bounds, effectively reaching near-linear time.
- Residue Table: The complexity is reduced to $\tilde{O}(u)$, improving upon the previous $O(u^{3/2})$ benchmark.
- Unbounded Knapsack Equivalence: The paper demonstrates that the All-Target Unbounded Knapsack problem is computationally equivalent to performing a (min, +) convolution. Specifically, it can be solved in $\tilde{O}(T(u) + t)$ time, where $T(u)$ is the time required for a (min, +) convolution of length $u$.
Discussion and Implications
This work provides a deep connection between high-level optimization problems and low-level algebraic operations. By showing that Unbounded Knapsack is tied to the complexity of (min, +) convolution, the authors identify a fundamental barrier: until a truly sub-quadratic algorithm for general (min, +) convolution is discovered, the Knapsack problem's complexity is unlikely to improve further.
While the results are primarily theoretical and focus on asymptotic complexity, the introduction of the kernel concept and witness propagation offers a new lens through which to view dynamic programming. Future work may involve exploring randomized approaches to simplify implementation or investigating the practical performance of these algorithms against traditional DP methods in real-world scenarios.
Summary updated