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:
- At each decision, the algorithm chooses the option that’s the locally optimal one. (I.e. looks best at that moment - the “Greedy” part).
- It doesn’t backtrack - once a choice is made, the algorithm doesn’t reconsider it.
- 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