Greedy algorithm

Correctness

One technique used to prove the optimality of greedy algorithms is an exchange argument. The exchange argument demonstrates that any solution different from the greedy solution is at most as good as the greedy solution. This proof pattern typically follows these steps:

1. Assume there exists an optimal solution different from the greedy solution.
2. Consider the first point where the optimal and greedy solutions differ.
3. Prove that exchanging the optimal choice for the greedy choice at this point cannot worsen the optimal solution.
4. Conclude by induction that the greedy solution is optimal.

Further examples

• In the fractional knapsack problem, one is given a list of items with weights and values. The goal is to choose fractional amounts of each item such that the total value is maximised, and the weight is below a fixed constraint. Unlike the knapsack problem, which is known to be NP-hard, the fractional knapsack problem admits a polynomial time greedy algorithm.
• Instances of the Frobenius coin problem admit greedy solutions. However, in some cases the greedy algorithm does not yield an optimal solution.
• The matching pursuit is an example of a greedy algorithm applied on signal approximation.
• A greedy algorithm finds the optimal solution to Malfatti's problem of finding three disjoint circles within a given triangle that maximize the total area of the circles; it is conjectured that the same greedy algorithm is optimal for any number of circles.
• In decision tree learning, greedy algorithms are commonly used, however they are not guaranteed to find the optimal solution.
  • One popular such algorithm is the ID3 algorithm for decision tree construction.
• A greedy algorithm constructs the Zeckendorf representation (or Fibonacci coding) of a natural number. Subtracting the largest Fibonacci number less than or equal to the natural number repeatedly gives its Zecekndorf representation. The greedy algorithm is extracted from the existence proof of the Zeckendorf representation. The uniqueness of the Zeckendorf representation guarantees that no other non-consecutive Fibonacci sum can give a different output.
• Fibonacci described a greedy algorithm for computing Egyptian fractions.
• Greedy algorithms appear in network routing. Using greedy routing, a message is forwarded to the neighbouring node which is "closest" to the destination. The notion of a node's location (and hence "closeness") may be determined by its physical location, as in geographic routing used by ad hoc networks. Location may also be an entirely artificial construct as in small world routing and distributed hash table.

Greedy algorithms on graphs

Graph theory is a rich source of greedy algorithms. Computing scientists frequently use greedy algorithms to compute graph invariants.

• Dijkstra's algorithm and the related A* search algorithm are verifiably optimal greedy algorithms for graph search and shortest path finding.
  • A* search is conditionally optimal, requiring an "admissible heuristic" that will not overestimate path costs.
• Kruskal's algorithm and Prim's algorithm are greedy algorithms for constructing minimum spanning trees of a given connected graph. They always find an optimal solution, which may not be unique in general.
• A greedy algorithm constructs a Huffman tree in Huffman coding.
• The Sequitur and Lempel-Ziv-Welch algorithms are greedy algorithms for grammar induction.
• A greedy algorithm finds the maximum independent set in a tree.

Greedy algorithms are also used to find upper bounds for the chromatic numbers. A simple example is the bound ${\displaystyle \chi (G)\le \mathrm{\Delta }(G)+1}$ obtained by a greedy algorithm. We begin by taking a vertex that has not been colored. Since it has at most ${\displaystyle \mathrm{\Delta }(G)}$ neighbours, at most ${\displaystyle \mathrm{\Delta }(G)}$ colors are used in adjacent vertices, leaving a color free for the vertex under consideration.

Greedy approximation algorithms

A solution to the NP-complete travelling salesman problem can be approximated by starting from an empty edge set and then adding the next cheapest edge which is a subgraph of a complete tour. This greedy algorithm has been proven to yield at most ${\displaystyle \mathrm{\Theta }(\log n)}$ times longer than the optimal tour.

Another example is that a solution for the 0-1 knapsack problem can be approximated by using the greedy algorithm for the fractional knapsack problem. This greedy algorithm has been proven to yield a solution at least half the value of the optimal solution.

Solutions for submodular maximization are approximated using a greedy algorithm which yields a solution at least half the value of the optimal solution.

Problems for which greedy algorithms are used to provide approximation algorithms include the set cover, load balancing, Steiner tree and independent set problem.