An efficient fully polynomial approximation scheme for the Subset-Sum Problem
Given a set of n positive integers and a knapsack of capacity c, the Subset-Sum Problem is to find a subset the sum of which is closest to c without exceeding the value c. In this paper we present a fully polynomial approximation scheme which solves the Subset-Sum Problem with accuracy ? in time and space O(n+1/?). This scheme has a better time and space complexity than previously known approximation schemes. Moreover, the scheme always finds the optimal solution if it is smaller than (1??)c. Computational results show that the scheme efficiently solves instances with up to 5000 items with a guaranteed relative error smaller than 1/1000.
fully polynomial approximation scheme subset-sum problem worst-case performance knapsack problem