I am having trouble understanding the proof of the theorem, which states that the greedy scheduling algorithm produces solutions of maximum size for the scheduling problem.

The proof that I am referencing is here: Greedy Algorithm Proof

I don't understand how the proof tells us to make the the problem smaller and smaller, iteratively to select the first element, see whats left, then select the first element of the new set, see what's left, and so on.

Does anyone have an easier way to understand the proof?

  • 2
    $\begingroup$ "For every iteration i of the loop, the set of jobs that have been added to the set A at the end of that iteration is a subset of some optimal set." this is quite crucial, do you understand it? The assumption? Proof of it? Which part of the proof you do not understand? It will be much easier to clarify the problematic part to you than making the whole new one. $\endgroup$
    – Evil
    Oct 30 '16 at 1:12
  • $\begingroup$ Can you elaborate on your first statement? I think that's what OP needs clarified. $\endgroup$
    – Gary
    Oct 30 '16 at 1:23
  • $\begingroup$ Please include the proof itself (with appropriate attribution) in your question. Links have a habit of breaking and your question will be completely incomprehensible to anyone in the future if that link goes away. $\endgroup$ Oct 30 '16 at 17:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.