Proof about optimality

  • Thread starter lolo94
  • Start date
  • #1
17
0

Homework Statement


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...

Homework Equations




The Attempt at a Solution

 

Attachments

  • Screenshot (25).png
    Screenshot (25).png
    43.6 KB · Views: 338
  • Screenshot (26).png
    Screenshot (26).png
    44.8 KB · Views: 338

Answers and Replies

  • #2
haruspex
Science Advisor
Homework Helper
Insights Author
Gold Member
2020 Award
35,879
6,598
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.
 

Related Threads on Proof about optimality

  • Last Post
Replies
2
Views
729
  • Last Post
Replies
5
Views
5K
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
13
Views
583
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
1
Views
6K
  • Last Post
Replies
1
Views
2K
Replies
3
Views
2K
Top