2021/03/15 by Majid Salimi, Salimi, Majid, Hamid Mala +1
Computer Science · Engineering · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Optimization and Packing Problems
paper · pdf · doi:10.48550/arxiv.2103.09080
openalex publication_date 2021/03/15 · openalex created_date 2021/03/29 · openalex updated_date 2026/07/28
The Unbounded Subset-Sum Problem (USSP) is defined as: given sum s and a set of integers W← \p1,…,pn\ output a set of non-negative integers \y1,…,yn\ such that p1y1+…+pnyn=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((p1)2+n) time complexity and O(p1) memory complexity, where p1 is the smallest element of W \citePH. This algorithm is polynomial in term of the number of inputs, but exponential in the size of p1. 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=1k-1qiqi+1-qi-qi+1, qi'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(n2) 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.