A Polynomial-Time Algorithm for Special Cases of the Unbounded Subset-Sum Problem
share
The Unbounded Subset-Sum Problem (USSP) is defined as: given sum s and a set of integers W←{p_1,…,p_n} output a set of non-negative integers {y_1,…,y_n} such that p_1y_1+…+p_ny_n=s. The USSP is an NP-complete problem that does not have any known polynomial-time solution. There is a pseudo-polynomial algorithm for the USSP problem with O((p_1)^2+n) time complexity and O(p_1) memory complexity, where p_1 is the smallest element of W <cit.>. This algorithm is polynomial in term of the number of inputs, but exponential in the size of p_1. Therefore, this solution is impractical for the large-scale problems. In this paper, first we propose an efficient polynomial-time algorithm with O(n) computational complexity for solving the specific case of the USSP where s> ∑_i=1^k-1q_iq_i+1-q_i-q_i+1, q_i's are the elements of a small subset of W in which gcd of its elements divides s and 2≤ k ≤ n. Second, we present another algorithm for smaller values of s with O(n^2) computational complexity that finds the answer for some inputs with a probability between 0.5 to 1. Its success probability is directly related to the number of subsets of W in which gcd of their elements divides s. This algorithm can solve the USSP problem with large inputs in the polynomial-time, no matter how big inputs are, but, in some special cases where s is small, it cannot find the answer.
READ FULL TEXT
