Approximation Schemes
Our goal is to develop a fully polynomial time approximation scheme (PTAS). Developing an approximation scheme often leads to acceptable results and improved run-time over the "optimal" problem instances. To critique an approximation scheme requires developing quantitative measures which can be used to compare different schemes. Two common measurements include: Performance Ratios and Runtime Dependency.
A Performance Ratiois an estimate of how "wrong" the solution is from the optimal solution. This is generally expressed as a ratio, ρ(n). The ratio is between the optimal solution, C*, and the approximate solution C. C is chosen here, as it typically represents a "cost" of the solution.
max(C/C*, C*/C) <= ρ(n)
A PTAS that can achieve a solution within a fixed ratio (the solution is bounded to within the ratio), is called a ρ(n)-apprxomation-algorithim. For example, if a PTAS algorithm can achieve a solution that bounded to be no more than twice the optimal solution (such as approximate TSP), then the algorithm is said to be a 2-approximation scheme.
To achieve an approximation, many PTAS algorithms are fed the original problem, and an ε, that represents the estimated error rate. This ε value now becomes part of the algorithm's run-time. An algorithm that runs in polynomial time on its input (excluding ε) is called a polynomial-time approximation scheme. In this case, the run-time remains constant despite the ε value. When the run-time of the algorithm is a factor of (1/ε) and the size n of the algorithm's input, then the algorithm is said to be a fully polynomial time approximation scheme. These algorithms fall into a special category of PTAS. By accepting more error, the run-time of the algorithm is reduced. Conversely, decreasing the amount of acceptable error causes the run-time of the algorithm to increase (possibly disproportionately to ε). Consider the following example of a FPTAS run-time:
O((1/ε)2n3)
Clearly, as epsilon is decreased, this algorithm will begin to exhibit increasing run-time. This should be an expected result. If one is asking for a "better" answer, the time to reach that answer should be expected to increase. If it was a "freebie" - it didn't take longer to ask for an extremely accurate answer than a bad answer, then why not ask for an answer whoose error is only infinitesimally inaccurate. There are no free lunches in the world! Thus, we should not expect such theoretically unlikely results.
Approximation Schemes
As stated above, the Integer Knapsack Problem is a "tough nut" to crack. Dynamic programming gives optimal results; but with a pseudo-polynomial run-time. The Approximate Knapsack Problem "fixes" this behavior by generating an approximate solution. The PTAS that is developed here is a fully-polynomial time approximation scheme for the Knapsack problem.
The weights of the items are scaled, such that they are all made multiples of each other. This the weights of the items will be rounded down to make each item a multiple of each other. First, an error rate, identified asε is selected, such that 0 < ε < 1. Using ε, an M value is computed:
This M value will serve as the common multiple for each of the items. Each of the items weights will be scaled by M: 
. After the items are scaled, one more change to the algorithm is needed. If every item in the set were selected into a knapsack, the knapsack would need to hold no more items than:
Thus, the size of the table is constrained to that factor. To solve the knapsack problem, construct the knapsack with 2n2/ε rows, and n columns. Fill the table with the values, and then, select the size of the knapsack that will hold the required value. This seemingly simple change has a dramatic change on the run-time: θ((1/ε)n3). In other words, this Knapsack problem is no longer specified in terms of the magnitudes of its values, and thus is no longer pseudo-polynomial in run-time.
