1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Proof about optimality

  1. Apr 27, 2016 #1
    1. The problem statement, all variables and given/known data
    I am trying to understand the optimality proof of the earliest finish time algorithm. I have attached the pdf which I am reading. It's just 2 pages. I don't understand what they mean with solution still feasible and optimal (but contradicts maximality of r). An explanation from scratch would be nice...

    2. Relevant equations


    3. The attempt at a solution
     

    Attached Files:

  2. jcsd
  3. Apr 28, 2016 #2

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    The proof supposes that the greedy algorithm matches the optimal solution, in regard to job finish times, up to and including the first r jobs, but not the first r+1. Clearly, if greedy is not optimal, there must be such an r, 0<=r<n. Note that optimal here just means that the finish time of the nth job is as early as it could be.
    In the second diagram, the r+1th job finishes at the same time in both greedy and optimal. That contradicts the definition of r, since it was defined to be such that greedy was not as good as optimal at the r+1th job.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Proof about optimality
  1. Proofs about Matrix (Replies: 5)

  2. Question about proof (Replies: 7)

  3. Proof about logarithms (Replies: 7)

Loading...