Seonglae ChoGreedy optimized choice for current state so Greedy typically takes linear time
It guarantees an approximation ratio of 63% for for submodular maximization problems in practice much higher. It also guarantees optimality for some problems. (Optimal substructure)
In greedy algorithm, you can’t escape from negative cycle and do not has shortest path.
Greedy Algorithms
Greedy Algorithm Notion