Subset Sum Problem - Polynomial Time Approximate Algorithm

Polynomial Time Approximate Algorithm

An approximate version of the subset sum would be: given a set of N numbers x₁, x₂, ..., x_N and a number s, output

• yes, if there is a subset that sums up to s;
• no, if there is no subset summing up to a number between (1 − c)s and s for some small c > 0;
• any answer, if there is a subset summing up to a number between (1 − c)s and s but no subset summing up to s.

If all numbers are non-negative, the approximate subset sum is solvable in time polynomial in N and 1/c.

The solution for subset sum also provides the solution for the original subset sum problem in the case where the numbers are small (again, for nonnegative numbers). If any sum of the numbers can be specified with at most P bits, then solving the problem approximately with c = 2−P is equivalent to solving it exactly. Then, the polynomial time algorithm for approximate subset sum becomes an exact algorithm with running time polynomial in N and 2P (i.e., exponential in P).

The algorithm for the approximate subset sum problem is as follows:

initialize a list S to contain one element 0. for each i from 1 to N do let T be a list consisting of x_i + y, for all y in S let U be the union of T and S sort U make S empty let y be the smallest element of U add y to S for each element z of U in increasing order do //trim the list by eliminating numbers close to one another //and throw out elements greater than s if y + cs/N < z ≤ s, set y = z and add z to S if S contains a number between (1 − c)s and s, output yes, otherwise no

The algorithm is polynomial time because the lists S, T and U always remain of size polynomial in N and 1/c and, as long as they are of polynomial size, all operations on them can be done in polynomial time. The size of lists is kept polynomial by the trimming step, in which we only include a number z into S if it is greater than the previous one by cs/N and not greater than s.

This step ensures that each element in S is smaller than the next one by at least cs/N and do not contain elements greater than s. Any list with that property consists of no more than N/c elements.

The algorithm is correct because each step introduces an additive error of at most cs/N and N steps together introduce the error of at most cs.