# Greedy proof: Correctness versus optimality

I am really confused after surveying a bunch of material online about correctness versus optimality proof for greedy algorithms. Some website even uses both correctness and optimal in the same sentence!

From my best unconfirmed understanding, the optimal proof uses "greedy stay ahead" where I need to show that greedy algorithm constructs a solution set that is no worse than the optimal set

The correctness proof utilizes the swapping argument to show that any difference between output set A and optimal set OPT can be eliminated by swapping the items in the optimal set.

Can someone clarify if I must only use the "greedy stay ahead" proof method for the optimal proof and not the correctness proof? And must I use the swapping argument (with contradiction) to show that swapping items in the optimal set?

Greedy stay ahead: http://www.cs.cornell.edu/Courses/cs482/2007sp/ahead.pdf

Swapping: http://www.cs.oberlin.edu/~asharp/cs280/handouts/greedy_exchange.pdf (Note that author states that this proves correctness and ends with prove optimality)

Instance where swapping was used to prove optimality, greedy stay ahead used to prove correctness: http://test.scripts.psu.edu/users/d/j/djh300/cmpsc465/notes-4985903869437/notes-5z-unit-5-filled-in.pdf

• Could edit or paste some reference about "greedy stay ahead proof method" that you're referencing above. Thanks. – jonaprieto Dec 18 '14 at 4:31

## 2 Answers

You can use whatever proof method you want. Proofs aren't even limited to existing patterns such as "greedy stay ahead" and "swapping". Indeed, in some cases, such as the greedy algorithm for maximizing a submodular function over a uniform matroid, the proof consists of adding together a bunch of inequalities expressing the fact that the random choice was (greedily) optimal.

Usually the proof that a greedy algorithm works compares itself against an optimal solution, though when proving approximation guarantees, it could be enough to compare the greedy solution to the theoretical maximum (a case in point is the derandomized version of the random 3SAT algorithm).

Also, I suspect that "correctness" and "optimality" mean the same thing.

A greedy algorithm splits the solution to a problem into steps, and at each step it selects some locally best next step. The splitting can typically be done in several different ways, several criteria of best next step are often available. In the extreme, take that one that (by looking forward) does give the best solution (not very "local", that one...).

When considering greedy algorithms, you either want it to give an optimal solution (and that is considered "correctness"), or you are interested in it giving a viable solution cheaply (as an heuristic, or an approximate algorithm), and are interested in how far it is from the optimal solution.