Two linear approximation algorithms for the subset-sum problem

摘要

In this paper we study the subset-sum problem (SSP), which is the problem of finding, given a set of n positive integers and a knapsack of capacity c, a subset the sum of which is closest to c without exceeding the value c. A short algorithm with worst-case guarantee 3/4 is introduced which outperforms Martello and Toth's 3/4 algorithm requiring a complexity time of O(n) instead of O(n~2). The second linear time algorithm reaches a 4/5 worst-case performance ratio. Both bounds are shown to be tight. Computational results on randomly generated and deterministic test problems are reported.