CODEWITHSUNDEEP
algorithmpseudocodegreedyproof
algorithmsMadness
algorithmsMadness

Reputation: 71

Proving optimality of greedy algorithm

Problem I came across is as follows:

We have n tasks with l_i and w_i being completion time and weight of task i. Come up with an algorithm that minimizes sum for all i of f_i * w_i where f_i is time when task i was finished. If for example some task i is scheduled first then f_i = t_i and if second then f_i = t_i + t_(first task).

I spent some time on this, I first thought that simply making the list of tasks by selecting tasks from highest weight to lowest weight will be good enough, but realized it's wrong, for example if we have 2 tasks:

1 task : w_i = 10, l_i = 100

2 task : w_i = 9, l_i = 1

if we selected the one with w_i 10 first then we would get 10*100 + 9*101 = 1909 but if we selected it second we would get 9*1 + 10*101 = 1019.

Now I think the optimal algo is the one that schedules tasks from highest ratio of w_i/l_i to the lowest, but I am not sure how to prove it. Could anyone help with it?

Upvotes: 1

Views: 354

Answers (2)

MrGreen
MrGreen

Reputation: 499

You are right the tasks should be scheduled according to decreasing order of w_i/L_i. Check the explanation of the proof of correctness given by Professor Tim Roughgarden Part 1 part 2

Upvotes: 1

mcdowella
mcdowella

Reputation: 19601

You should be able to show that if the tasks are not arranged as you suggest you can improve the schedule by swapping two adjacent tasks that are in the wrong order. If you subtract total weighted completion times for these two cases you should end up looking at an expression for the difference in the weighted completion times of something like

L1W1 + (L1 + L2)W2 - [L2W2 + (L2 + L1)W1] and finding that you gain by reversing the order if L1/W1 and L2/W2 compare in the wrong direction.

Upvotes: 1

Related Questions