Linear Time Approximation Algorithms for Subset Sum
Liliana Grigoriu · 2025
Given a multiset of n positive integers and a target sum S, the subset sum problem is to find a subset such that the sum of its elements is as close as possible to S without exceeding S. We present a family of polynomial-time approximation algorithms for subset sum with a worst-case approximation ratio of 1 - 1/(k+1) assuming that k is constant. The maximum number of times a linear-time procedure could be called within the algorithms, which depends on k, is determined computationally for sample values of k up to k=80. For example, for k=10, this number is 13, for k=20 it is 2712, and for k=40 it is 215306. Our approach generalizes and improves upon a previous work by Kellerer et al. where 3/4 and a 4/5 approximation algorithms for the subset sum problem were presented. We also comment on how the algorithms can be parallelized. The simplicity of the algorithms allows for fast implementation.