Greedy algorithm

A greedy algorithm solves an optimization problem where a solution is composed of partial solutions to subproblems by considering exactly one decomposition of the problem. In this sense, a greedy algorithm is a special case of a dynamic programming algorithm. Uriel Feige notes that:

[Greedy algorithms] may be viewed as the ultimate form of dynamic programming, in which only one partial solution is maintained. The problem needs to have much more structure for this approach to work.

A classic example of a problem solved by a greedy algorithm is the activity selection problem. Given a collection of tasks which can be done between allotted time intervals, we have to determine the maximum number of tasks that can be done. A greedy algorithm in $O(\log(n))$ which solves this problem sorts the tasks by the end time and then repeatedly chooses the first task that begins after the last task ended.

Stephen Cook notes that greedy algorithms are part of a standard toolkit used in the design of polynomial algorithms.Many classic algorithms in computer science such as Prim's Algorithm, Kruskal's algorithm, and Dijkstra's algorithm all use greedy properties in their design. In number theory, Fibonacci described an greedy algorithm for computing Egyptian fractions for computing the Egyptian fraction decomposition of a rational number.

Mathematicians frequently use greedy strategies in proofs as well. Here the term greedy is interpreted in a more broad sense, where a solution is updated incrementally without undoing previous changes. A classic example is what Raphael Yuster refers to as the greedy proof that every tournament in graph contains a Hamiltonian path.

Characterizations

Since there is no formal definition of what a greedy algorithm is, a complete characterization of when a problem admits a greedy algorithm as a solution is not known. However, special cases have been identified. Jack Edmonds showed that a greedy algorithm can be used to solve a class of linear combinatorial optimization problems with a matroid structure.

Later Bernhard Korte and László Lovász characterized a broader class of optimization problems by introducing the notion of a greedoid. This allowed, for example, a proof of the optimality of Prim's algorithm.

Algorithms which undo past steps are not greedy. For example, the Gale-Shapley algorithm is not a greedy algorithm since although it constructs a solution by choosing the current best pairing, in the process, existing solutions may be modified.

Correctness

One technique used to prove the optimiality 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 greedy solution
4. Conclude by induction that the greedy solution is optimal.

Examples of how a greedy algorithm may fail to achieve the optimal solution.

Starting from A, a greedy algorithm that tries to find the maximum by following the greatest slope will find the local maximum at "m", oblivious to the global maximum at "M".

To reach the largest sum, at each step, the greedy algorithm will choose what appears to be the optimal immediate choice, so it will choose 12 instead of 3 at the second step, and will not reach the best solution, which contains 99.

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.
• 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 frequently 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 $\chi (G)\leq \Delta (G)+1$ obtained by a greedy algorithm. We begin by taking a vertex that has not been colored. Since it has at most $\Delta (G)$ neighbours, at most $\Delta (G)$ colors are used in adjacent vertices, leaving a color free for the vertex under consideration.

Greedy approximation algorithms

In many cases, a greedy strategy does not produce an exact solution, but can yield solutions that approximate an exact solution in a reasonable amount of time.

For example, 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 $\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.

See also

• Best-first search
• Epsilon-greedy strategy
• Greedy algorithm for Egyptian fractions
• Greedy source
• Hill climbing
• Horizon effect
• Matroid

References

Sources

• Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001). "16 Greedy Algorithms". Introduction To Algorithms. MIT Press. pp. 370–. ISBN 978-0-262-03293-3.
• Gutin, Gregory; Yeo, Anders; Zverovich, Alexey (2002). "Traveling salesman should not be greedy: Domination analysis of greedy-type heuristics for the TSP". Discrete Applied Mathematics. 117 (1–3): 81–86. doi:10.1016/S0166-218X(01)00195-0.
• Bang-Jensen, Jørgen; Gutin, Gregory; Yeo, Anders (2004). "When the greedy algorithm fails". Discrete Optimization. 1 (2): 121–127. doi:10.1016/j.disopt.2004.03.007.
• Bendall, Gareth; Margot, François (2006). "Greedy-type resistance of combinatorial problems". Discrete Optimization. 3 (4): 288–298. doi:10.1016/j.disopt.2006.03.001.
• Feige, U. (1998). "A threshold of ln n for approximating set cover" (PDF). Journal of the ACM. 45 (4): 634–652. doi:10.1145/285055.285059. S2CID 52827488. Archived (PDF) from the original on 2022-10-09.
• Nemhauser, G.; Wolsey, L.A.; Fisher, M.L. (1978). "An analysis of approximations for maximizing submodular set functions—I". Mathematical Programming. 14 (1): 265–294. doi:10.1007/BF01588971. S2CID 206800425.
• Buchbinder, Niv; Feldman, Moran; Naor, Joseph (Seffi); Schwartz, Roy (2014). "Submodular maximization with cardinality constraints" (PDF). Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms. Society for Industrial and Applied Mathematics. doi:10.1137/1.9781611973402.106. ISBN 978-1-61197-340-2. Archived (PDF) from the original on 2022-10-09.
• Krause, A.; Golovin, D. (2014). "Submodular Function Maximization". In Bordeaux, L.; Hamadi, Y.; Kohli, P. (eds.). Tractability: Practical Approaches to Hard Problems. Cambridge University Press. pp. 71–104. doi:10.1017/CBO9781139177801.004. ISBN 9781139177801.
• Papadimitriou, Christos H.; Steiglitz, Kenneth (1998). Combinatorial Optimization: Algorithms and Complexity. Dover.

External links

• "Greedy algorithm", Encyclopedia of Mathematics, EMS Press, 2001 [1994]
• Gift, Noah. "Python greedy coin example".