Greedy Algorithms

A greedy algorithm repeatedly executes a procedure which tries to maximize the return based on examining local conditions, with the hope that the outcome will lead to a desired outcome for the global problem. In some cases such a strategy is guaranteed to offer optimal solutions, and in some other cases it may provide a compromise that produces acceptable approximations.

Typically, the greedy algorithms employ simple strategies that are simple to implement and require minimal amount of resources.

Prim’s Minimal Spanning Tree Algorithm

Grows a tree by adding in each step a branch with minimal cost. Despite this “short sight” approach, the outcome is optimal.

Kruskal’s Minimal Spanning Tree Algorithm

At each stage, the edge with the least cost is processed.

 Dijkstra’s Single-Source Shortest Paths Algorithm

Establish the shortest path between a single source node and all of the other nodes in a graph.

Greedy algorithm: Add an edge that connects a new node to those already selected. The path from the source to the new node should be the shortest among all the paths to nodes that have not been selected yet.

        

The algorithm has time complexity O(|V |²). (Note the similarity and difference relatively to Prim’s algorithm.)

Coin Change

The problem asks to provide a change for a specified amount, using a minimal number of coins. A greedy algorithm may at each stage employ the criteria of providing the largest available coin which is not greater than the amount still owed.

Egyptian Fractions

Each fraction can be expressed as a sum of different fractions with unit numerators. Such representations have been used by the ancient Egyptians.

A given fraction might have more than one Egyptian representation. A greedy algorithm, for finding such a representation, can at each stage add to the sum the largest unit fraction which does not cause the sum to exceed the fraction. Fibonacci proved that this greedy algorithm is guaranteed to halt.

Map Coloring

The map coloring problem asks to assign colors to the different regions, where adjacent regions are not allowed to have the same color. There is no general algorithm to assign minimal number of colors, yet each map has an assignment which uses no more than four colors.

A greedy approach repeatedly choose a new color, and assign it to as many regions as possible.

Voting Districts

Given an integer number N, and a map in which each region is assigned an integer number (= population size), the problem asks to create N district with minimal deviation of population. The regions in each district must be connected.

A greedy algorithm can start by choosing the N biggest regions as cores of the different districts. Then, in each iteration, the largest unassigned region, among those that are adjacent to assigned regions, is assigned to the district with the smallest population.

Vertex Cover

A vertex cover of a graph G = (V, E) is a subset of nodes, where the nodes of the subset are attached all the edges of the graph. The problem of finding a vertex cover of minimum size is NP-complete, implying the non-existence of efficient algorithms for solving the problem accurately.

A greedy algorithm may provide approximated solutions, by selecting in each stage a vertex which covers the most edges that have not been covered yet.

0/1 Knapsack

Given a set of N item (v_i, w_i), and a container of capacity C, find a subset of the items that maximizes the value  v_i while satisfying the weight constraints  w_i < C. This problem is a NP-hard problem, requiring an exhaustive search over the 2^N possible combinations of items, for determining an exact solution.

A greedy algorithm may consider the items in order of decreasing value-per-unit weight v_i/w_i. Such an approach guarantees a solution with value no worst than 1/2 the optimal solution.