[Solved]: Greedy proof: Correctness versus optimality

Problem Detail: 

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

Asked By : John Swoon

Answered By : Yuval Filmus

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/35467