Editing Subset sum problem (section)

== Polynomial time approximation algorithms ==

{{More citations needed section|date=February 2021}}

Suppose all inputs are positive. An [[approximation algorithm]] to SSP aims to find a subset of ''S'' with a sum of at most ''T'' and at least ''r'' times the optimal sum, where ''r'' is a number in (0,1) called the ''approximation ratio''.

=== Simple 1/2-approximation ===
The following very simple algorithm has an approximation ratio of 1/2:<ref name=":1">{{Cite journal|last1=Caprara|first1=Alberto|last2=Kellerer|first2=Hans|last3=Pferschy|first3=Ulrich|date=2000-02-01|title=The Multiple Subset Sum Problem|url=https://doi.org/10.1137/S1052623498348481|journal=SIAM Journal on Optimization|volume=11|issue=2|pages=308–319|doi=10.1137/S1052623498348481|issn=1052-6234}}</ref>

* Order the inputs by descending value;
* Put the next-largest input into the subset, as long as it fits there.

When this algorithm terminates, either all inputs are in the subset (which is obviously optimal), or there is an input that does not fit. The first such input is smaller than all previous inputs that are in the subset and the sum of inputs in the subset is more than ''T''/2 otherwise the input also is less than T/2 and it would fit in the set. Such a sum greater than T/2  is obviously more than OPT/2.

=== Fully-polynomial time approximation scheme{{Anchor|FPTAS}} ===
The following algorithm attains, for every <math>\epsilon>0</math>, an approximation ratio of <math>(1-\epsilon)</math>. Its run time is polynomial in {{mvar|n}} and <math>1/\epsilon</math>. Recall that ''n'' is the number of inputs and ''T'' is the upper bound to the subset sum.
 initialize a list ''L'' to contain one element 0.
 
 '''for each''' ''i'' from 1 to ''n'' '''do'''
     let ''U<sub>i</sub>'' be a list containing all elements ''y'' in ''L'', and all sums ''x<sub>i</sub>'' + ''y'' for all ''y'' in ''L''.
     sort ''U<sub>i</sub>'' in ascending order
     make ''L'' empty 
     let ''y'' be the smallest element of ''U<sub>i</sub>''
     add ''y'' to ''L''
     '''for each''' element ''z'' of ''U<sub>i</sub>'' in increasing order '''do'''
         <u>// Trim the list by eliminating numbers close to one another</u>
         <u>// and throw out elements greater than the target sum ''T''.</u>
         '''if''' ''y'' +  ''ε T''/''n'' < ''z'' ≤ ''T'' '''then'''
             ''y'' = ''z''
             add ''z'' to ''L''
 
 '''return''' the largest element in ''L.''

Note that without the trimming step (the inner "for each" loop), the list ''L'' would contain the sums of all <math>2^n</math> subsets of inputs. The trimming step does two things:

* It ensures that all sums remaining in ''L'' are below ''T'', so they are feasible solutions to the subset-sum problem.
* It ensures that the list L is "sparse", that is, the difference between each two consecutive partial-sums is at least <math>\epsilon T/n</math>. 

These properties together guarantee that the list {{mvar|L}} contains no more than <math>n/\epsilon</math> elements; therefore the run-time is polynomial in <math>n/\epsilon</math>.

When the algorithm ends, if the optimal sum is in {{mvar|L}}, then it is returned and we are done. Otherwise, it must have been removed in a previous trimming step.  Each trimming step introduces an additive error of at most <math>\epsilon T/n</math>,  so {{mvar|n}} steps together introduce an error of at most <math>\epsilon T</math>. Therefore, the returned solution is at least <math>\text{OPT}-\epsilon T</math> which is at least <math>(1-\epsilon)\text{OPT}</math> .

The above algorithm provides an ''exact'' solution to SSP in the case that the input numbers are small (and non-negative). If any sum of the numbers can be specified with at most {{mvar|P}} bits, then solving the problem approximately with <math>\epsilon = 2^{-P}</math> is equivalent to solving it exactly. Then, the polynomial time algorithm for approximate subset sum becomes an exact algorithm with running time polynomial in {{mvar|n}} and <math>2^P</math> (i.e., exponential in {{mvar|P}}).

Kellerer, Mansini, Pferschy and Speranza<ref>{{Cite journal|last1=Kellerer|first1=Hans|last2=Mansini|first2=Renata|last3=Pferschy|first3=Ulrich|last4=Speranza|first4=Maria Grazia|date=2003-03-01|title=An efficient fully polynomial approximation scheme for the Subset-Sum Problem|journal=Journal of Computer and System Sciences|language=en|volume=66|issue=2|pages=349–370|doi=10.1016/S0022-0000(03)00006-0|issn=0022-0000|doi-access=}}</ref> and Kellerer, Pferschy and Pisinger<ref name="knapsack">{{cite book|author1=Hans Kellerer|title=Knapsack problems|url=https://books.google.com/books?id=u5DB7gck08YC&pg=PA97|page=97|year=2004|publisher=Springer|isbn=9783540402862|author2=Ulrich Pferschy|author3=David Pisinger}}</ref> present other FPTASes for subset sum.