Greedy Algorithms

• Picks the local optimal solutions at each stage
  • Hopes that picking the best looking choice each time results in the overall best
• Does not guarantee globally optimal solution
  • Trades optimality for faster performance
• Examples
  • Dijkstra’s Algorithm
  • Prim’s Algoritm
  • Kruskal’s Algoritm
  • Huffman Trees
  • Coin Change
  • Interval Scheduling
  • Interval Partitioning
  • Scheduling to Minimize Lateness
  • Bin packing
    • Will not always give correct solution
  • Traveling Salesman
    • Exact solution: $O(2^n\cdot n^2)$
    • Greedy: $O(n^2\log n)$ and within 1.5x of optimal

Examples

Bin Packing

• The minimum number of bins of a certain size that can store some boxes of various sizes
• Can be modified into an n-sum problem
• Greedy Solution
  • First fit: scan the bins and place the new item in the first bin that is large enough
  • Best fit: Scan the bins and place the new item in the bin that finds the spot that creates the smallest empty space

Graph Coloring

• How can we assign a color to every node in the graph such that no adjacent nodes have the same color
• Brute Force Solution
  • Steps
    1. Go through all combinations of colors for the graph
    2. Check each combination until we find the first valid solution
  • $O(n{2}^n)$ time complexity
• Greedy Solution
  • A “good enough solution”
    • Uses more colors
  • $O(V^2)$ time complexity
  • Steps
    • Color the starting vertex with the fist color
    • For all remaining vertices
      • If all the colors are used my adjacent vertices
        • Make a new color and assign it to that vertex
      • Else
        • Color it with the first color that has not been used by any adjacent vertex
• Number of colors
  • Max: V (complete graph: every single vertex is connected)
  • Min: 2 (the graph is a single cycle or line)