On Problems Related to Unbounded SubsetSum: A Unified Combinatorial Approach
share
Unbounded SubsetSum is a classical textbook problem: given integers w_1,w_2,⋯,w_n∈ [1,u], c,u, we need to find if there exists m_1,m_2,⋯,m_n∈ℕ satisfying c=∑_i=1^n w_im_i. In its all-target version, t∈ℤ_+ is given and answer for all integers c∈[0,t] is required. In this paper, we study three generalizations of this simple problem: All-Target Unbounded Knapsack, All-Target CoinChange and Residue Table. By new combinatorial insights into the structures of solutions, we present a novel two-phase approach for such problems. As a result, we present the first near-linear algorithms for CoinChange and Residue Table, which runs in Õ(u+t) and Õ(u) time deterministically. We also show if we can compute (min,+) convolution for n-length arrays in T(n) time, then All-Target Unbounded Knapsack can be solved in Õ(T(u)+t) time, thus establishing sub-quadratic equivalence between All-Target Unbounded Knapsack and (min,+) convolution.
READ FULL TEXT