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 O(min{n·1/ε,n+1/ε2log(1/ε)}) 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.