Greedy Proofs

What is greedy algorithm’s partial solution suppose to prove?

That is is at least as good as any optimal solutions partial solution

What is the “greedy stays ahead” algorithm similar to?

Thjink of it like a race: the greedy choice always stays ahead

Give some example of what “ahead” could mean.

Earlier finish time, smallest cost so far, more tasks scheduled

What are the 4 things to look out for that will let you know when to use “greedy stays head”?

✔ You can compare prefix-by-prefix progress.
✔ The greedy solution and optimal solution build solutions in the same order.
✔ It’s natural to define a partial measure of progress.
✔ The greedy criterion relates directly to an ordering rule (sort-by…).

What are some classic problems using GSA?

• Interval scheduling (sort by earliest finish time)
  

• Scheduling to minimize lateness
  

• Minimizing average completion time (sort by shortest processing time)
  
  

What is the exchange argument trying to show?

Show that any optimal solution can be gradually transformed into the greedy solution without making it worse.

What is a hint for exchange?

Think of it as:
"if your optimal solution doesn't follow the greedy choice, swap something to make it follow greedy — and don't lose optimality."

What should you use exchange?

Use an exchange argument when:

✔ The greedy choice makes sense locally but does not naturally create a prefix-by-prefix ordering.
✔ You can “fix” any optimal solution that violates the greedy rule.
✔ Feasible swaps exist.
✔ The solution is more like a set (not inherently ordered by time or progress).

What are some classic problems using Exchange Arguments?

• Minimum Spanning Tree (Kruskal’s / Prim’s)
  
  

• Activity selection (also works with stays-ahead, but exchange is very common)
  
  

• Scheduling to minimize weighted completion time
  
  

• Fractional knapsack
  
  

Proof of optimality of greedy set cover heuristic (partial)

What should you use when you want to compare partial progress (prefixes) between greedy and optimal?

Stays Ahead

What should you use when the solution is an unordered set where swaps make sense?

Exchange

What do you use when greedy makes a local choice that isn’t about order but about structure (e.g., minimum edge)?

Exchange

What do you use when you can identify the “first place” where optimal and greedy differ and fix it?

Exchange

What should you use if the greedy action involve sorting and choosing the first valid item?

Stays Ahead because sorted order —> natural prefix structure

You want stay ahead when problems involve:

✔ Problems involving line-like order (distance along a road, time, deadlines)

→ Stays-ahead

✔ Problems where greedy pushes forward in a sequence

→ Stays-ahead

✔ Problems involving “first, second, third...” decisions

→ Stays-ahead

✔ Problems where you can compare greedy’s i-th choice to optimal’s i-th

→ Stays-ahead is expected.

More stay ahead examples include:

• Gas station problem (this one)
  
  

• Interval scheduling (earliest finish time)
  
  

• Scheduling to minimize lateness
  
  

• Fractional knapsack
  
  

• Minimizing average completion time (SPT rule)
  
  

• Anything involving “go as far as possible” or “earliest something”
  
  

It is exchange when:

• There is no natural order of choices
  
  

• The solution is a set, not a sequence
  
  

• Partial solutions are not meaningful
  
  

Swapping is possible

Examples of exchange are:

• Minimum Spanning Tree (Kruskal/Prim)
  
  

• Set cover style arguments
  
  

• Matroid greedy proofs
  
  

Scheduling problems with weighted objectives (if ordering isn’t simple)