Today, in my self-lead studies, I found out about greedy algorithms, more specifically, a greedy approach to solve The Weighted Job Scheduling Problem.

I understand how the solution is implemented but, I'd love to see a proof of correctness for this solution (i.e. partial correctness and termination). If anyone can help me understand why this solution is correct mathematically in a general form, that'd really great!

  • $\begingroup$ Have you ever read the proof for Kruskal's algorithm? A proposition similar to the proposition $P$ there can be proved by induction for this problem. If you can write an answer, I can check and upvote. $\endgroup$ – John L. May 20 at 4:13
  • $\begingroup$ What is the weighted job scheduling problem? What is the greedy algorithm used to solve it? $\endgroup$ – Yuval Filmus May 20 at 5:49
  • $\begingroup$ Hi @JohnL. I have read the proof you linked, but do not see how it's related. Can you link me to a proof of a solution (dynamic or greedy) to the Weighted Job Scheduling problem, please? :) $\endgroup$ – Kapernski May 20 at 6:52
  • $\begingroup$ Try proving the following proposition by induction: If $A$ is the arrangement of the jobs at each stage of your algorithm right after a job is selected, there is an optimal arrangement of the jobs that extends $A$. $\endgroup$ – John L. May 21 at 23:09

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.