Definition: An algorithm
to solve an optimization problem that runs in polynomial time
in the length of the input and outputs a solution that is guaranteed to be close
to the optimal solution. ``Close'' has some well-defined sense called
the performance guarantee.
