The Relative Error of an Approximate Algorithm

For approximate algorithms, we will be interested in a quantity called the relative error.
We will only be asked to calculate the Relative Error in simple cases.


RELATIVE ERROR will primarily be important to us for theoretical reasons since we will be able to calculate the Optimal Solution only for simple cases.  A complete discussion of evaluating the performance of an approximate algorithm is beyond the scope of this course BUT, two factors which are important are: (1) worst-case performance and (2) average performance.

The relative error tells us how close the approximate solution is to the optimal solution.