- No formal definition
- ⋯ can design many different greedy algorithms for same problem
- greedy algorithms build the solution step-by-step
- ⋯ making local decisions to improve the solution
- Often, this short-sightedness does not help in finding an optimal solution
- But, if the problem has some underlying structure, then some clever greedy algorithm can find an (approximately) optimal solution
- Often analysed by showing that greedy is (approximately) as good as optimal algorithm at each step
Pros vs Cons of greedy algorithms
Pro:
- Very intuitive
- Easy to explain and implement
- Most heuristics are based on some greedy choices
- Sometimes can be shown to be (approximately) correct
Cons:
- Many different notions of greedy
- Local “correct” steps might not mean global correctness
- Quite often does not lead to optimal solutions
- Avoid using a greedy algorithm in practice without analysing it