Optimal solution for a scheduling problem where there are n jobs (1,2,3,..,n) where a job i has a weight Wi, length Li. (0 < i <=n)
Prove that the optimal solution is to order the jobs in decreasing Wi/Li (proportional to weight or importance and inversely proportional to length).
Proof 1: (prove without ties, i.e Wi/Li are unique). Hint: Use exchange argument and contradiction
Proof 2: (prove even with ties, i.e Wi/Li may not be unique). Hint: Prove that greedy algorithm is at least as good as any other solution and note the bubble sort inside the proof argument.
Prove that the optimal solution is to order the jobs in decreasing Wi/Li (proportional to weight or importance and inversely proportional to length).
Proof 1: (prove without ties, i.e Wi/Li are unique). Hint: Use exchange argument and contradiction
Proof 2: (prove even with ties, i.e Wi/Li may not be unique). Hint: Prove that greedy algorithm is at least as good as any other solution and note the bubble sort inside the proof argument.
No comments:
Post a Comment