Linear-time approximation algorithms for minimum subset sum and subset sum

We present a linear-time approximation algorithm for minimum subset sum, which has better worst-case approximation factor (6/5) than previous linear-time algorithms for this problem. We also present a generalization of the scheme used to derive the algorithm, which can be used to obtain algorithms with approximation ratios of (k+1)/k. In addition, we present a family of linear-time approximation algorithms for subset sum with worst-case approximation factors of k/(k+1) assuming that k is constant.

Article

Download

View Linear-time approximation algorithms for minimum subset sum and subset sum