What:

A specific type of Greedy Algorithms. These are for when getting exact solutions are largely impractical. Ideally they:

  • Run in polynomial time.
  • Compute a solution that’s “close” to the optimal one. (I.E. Reasonably accurate)

Problem: What’s “close to optimal”?

Key Idea

Well if our solution is not far from something that’s even smaller than the optimal, then it surely isn’t far from the optimal.

Thus, a technique:

Bound the optimal solution from below (for minimisation problems - like below) and above (for maximisation problems).

Characteristics:

  1. At each decision, the algorithm chooses the option that’s the locally optimal one. (I.e. looks best at that moment - the “Greedy” part).
  2. It doesn’t backtrack - once a choice is made, the algorithm doesn’t reconsider it.
  3. They’re simple and fast.

Approximation Ratio:

Specific Examples:

Approximating NP Hard Problems:

It’s really hard to approximate some problems. The best approximation we can get is: Polynomial Time Approximation Scheme