CODEWITHSUNDEEP
algorithmjob-schedulinggreedy
Walt
Walt

Reputation: 1426

Proof of optimality of a greedy solution to job sequencing

In this Job Sequencing Problem, how do we prove that the solution which greedy approach will provide is a optimal one?

Moreover, I am also not able to figure out the O(n) solution as the author later is claiming

It can be optimized to almost O(n) by using union-find data structure.

Upvotes: 7

Views: 5994

Answers (4)

noname
noname

Reputation: 66

The given proof is not complete. Namely, the sentence "the job i'at pos in S* cannot be of larger profit than i" is not proven, and I think it cannot be. Anyhow, there can be proven that the statement holds even if job i has profit larger or equal to i''.

for complete proof see http://ggn.dronacharya.info/CSEDept/Downloads/QuestionBank/Even/VI%20sem/ADA/Section-B/job-scheduling1.pdf

Upvotes: 0

Codor
Codor

Reputation: 17605

The optimality of the greedy solution can be seen by an exchange argument as follows. Without loss of generality, assume that all profits are different and that the jobs are sorted in decreasing order of profits.

Fix a solution S. From this solution, delete every job that misses its deadline. As by this transformation every job finishes within its deadline, the resulting solution S1 is still optimal. For job i, consider the interval I_i:=[0,min(n,deadline(i))] (as in the greedy algorithm). In this interval, to the right of job i, there are only jobs with larger processing time (if not, they either would have been considered earlier by our ordering, or they could be exchanged witout violation of their deadlines). Place job i to the rightmost position possible in I_i.

In total, we have the following statement.

Each solution S can be transformed into a solution S' with the following propoerties.

  1. S' contains every job of S which finishes before its deadline.
  2. For every job i in S, all jobs after i in I_i have a larger processing time.
  3. For every job i in S, there is no idle time after i in I_i.
  4. S' has the same objective value as S.

In particular, there exists an optimal solution S* with the properties above. Let S be the algorithm generated by the greedy algorithm. Note that S also has the properties 2 and 3 above. Let i be the first job which occurs in S but not in S*. Let pos be the time slot of i in S. If pos was empty in S*, S* could be improved by adding i, in contradiction to the optimality of S*. If pos was not empty in S*, the job i'at pos in S* cannot be of larger profit than i, since otherwise the greedy algorithm would have chosen i' to be at pos in S. Hence, it must be of lower profit than i. This means that it can be deleted and replaced by i in S*, which also contradicts the optimality of S*.

Upvotes: 4

kraskevich
kraskevich

Reputation: 18556

  1. Proof of correctness. Let's assume that it is not correct. What does it mean? It means that at some step we have thrown away a job because it was not possible to add it without removing an already taken one. If we had removed an already taken one and put the current one into its time slot, we wouldn't have changed anything for the next jobs(the set of occupied time slots would have been the same). But the total profit would have reduced. Thus, a solution produced by this algorithm is optimal.

  2. Making it faster than O(n ^ 2). To do it, we need to find the rightmost free position to the left from the given one quickly. If we use a union-find structure to maintain a group of occupied position, we can just find the group where a deadline of the current job is located and an take element located to the left from it. But it is still O(n log n) because of the sorting.

Upvotes: 1

Dima
Dima

Reputation: 40500

Consider a job worth 2 points with deadline 4, and three jobs worth 1 point each, with deadline 3. This disproves the optimality of the "greedy" algorithm: it is more profitable to do the three cheaper jobs first, before the more expensive one.

As for the O(n^2) vs. O(n), I think both claims are wrong too. The "greedy" algorithm, as described, consists of sorting the jobs - O(nlogn) - plus a single scan of the sorted list, filling the solution sequence slots - O(n) - and is therefor O(nlogn).

To make it linear, one would have to do something about sorting, such use using radix sort, which can be considered linear for practical purposes.

Upvotes: 0

Related Questions