Question

Submit a brief history (in chronological order) of the "Greedy Algorithm". Where did it originated? Who discovered it? Etc.

Answer 1

Greedy Algorithms were conceptualized in 1950s as part of graph walking algorithms. It was E. Djikstra who conceptualized a greedy algorithm to create minimal spanning tree - The motivation behind this was to shorten the route span in Amsterdam. During the same time, Prim and Kruskal developed their own optimization algorithms based on greedy approach to minimize the cost along weighted paths.

In 1970s, Cormen, Rivest, and Stein, in their famous book Introduction To Algorithms, proposed recursive restructuring for solutions based on greedy approach. In 2005, Greedy Approach was registered as a separate optimization strategy in NIST.

In the current world, Greedy Algorithms and approach find many applications in AI and on web like OSPF and some network packet switching protocols.