Greedy algorithm (nonfiction)

Greedy algorithms determine minimum number of coins to give while making change. These are the steps a human would take to emulate a greedy algorithm to represent 36 cents using only coins with values {1, 5, 10, 20}. The coin of the highest value, less than the remaining change owed, is the local optimum. (In general the change-making problem requires dynamic programming to find an optimal solution; however, most currency systems, including the Euro and US Dollar, are special cases where the greedy strategy does find an optimal solution.)

A greedy algorithm is an algorithmic paradigm that follows the problem solving heuristic of making the locally optimal choice at each stage with the intent of finding a global optimum. In many problems, a greedy strategy does not usually produce an optimal solution, but nonetheless a greedy heuristic may yield locally optimal solutions that approximate a globally optimal solution in a reasonable amount of time.

For example, a greedy strategy for the traveling salesman problem (which is of a high computational complexity) is the following heuristic: "At each step of the journey, visit the nearest unvisited city." This heuristic doesn't intend to find a best solution, but it terminates in a reasonable number of steps; finding an optimal solution to such a complex problem typically requires unreasonably many steps. In mathematical optimization, greedy algorithms optimally solve combinatorial problems having the properties of matroids, and give constant-factor approximations to optimization problems with submodular structure.

In the News

• 

  January 10, 2018: The Algorithmic Paradigm Treaty Organization (APTO) files math crime charges against greedy algorithms.

Fiction cross-reference

• Crimes against mathematical constants
• Gnomon algorithm
• Gnomon Chronicles
• Mathematics

Nonfiction cross-reference

• Algorithm (nonfiction)
• Algorithmic paradigm (nonfiction)
• Greedy coloring (nonfiction)
• Mathematics (nonfiction)

External links:

• Greedy algorithm @ Wikipedia