I'm lost on a simple proof of a greedy algorithm

[LordEricO]

Hello,

I'm reading about greedy algorithms in "Algorithm Design" by Jon Kleinberg and Eva Tardos. Specifically, the "scheduling to minimize lateness" example. Basically, the goal is to schedule jobs each with a deadline on a single resource so that the lateness, or the finish time - deadline time is minimized (lateness cannot be negative). The solution is to take the jobs in increasing deadlines with no idle time. The proof involves an "inversion"; a situation where job j is scheduled after job i even though the deadline for j is before the deadline for i. It was proved that if an inversion exists between job a and job b, then there must be an inversion between two jobs i and j who are scheduled back to back. The claim is that swapping the two jobs that make up the inversion, i and j, does not increase the overall lateness. This is where I am confused.... Consider this example.

Before:

| <-2-> | <-2-> | <-2-> | <----8----> |
d(j) d(i) JOB I JOB j

where d(x) is the deadline of job x. The total lateness of I+J is 4+14=18. This is clearly an inversion.

After the swap:

| <-2-> | <-2-> | <----8----> | <-2-> |
d(j) d(i) JOB j JOB i

The total lateness is 12+12=24.

Doesn't this show that an inversion does not always lower the lateness or it keep the same, and hence the proof is faulty? Am I missing something?

Thanks for the help,

Eric

[egawtry]

Sorry, but I stared at your example for 20 minutes, and I don't understand it. Could you please clarify?

1. You have several functions used - what are their declarations?
2. What do you mean by "inversion" and "lateness"? I don't seem to recall that one from any of the CS courses I took. Maybe I am getting old. I read your quick explanation and it didn't help.
3. What do your diagrams mean? Are those events that take place simultaneously or sequentially? Are those functions supposed to line up under them?

:confused::sick::cool:

-Erik

[LordEricO]

Ok... wow, I didn't realize the formatting on those diagrams came out so terribly. Basically, each job has a deadline. The deadline for job number x is denoted as d(x). The goal of this problem is to schedule all jobs so that none overlap and the total lateness of all jobs is minimized. Lateness is defined as the amount of time between the deadline of a job, and when it was actually completed. So if a job is completed anytime before or at the deadline, its lateness is 0. If a deadline for job x is at time 5 and job x is scheduled to finish at time 7, there is a lateness of 2. (time units are arbitrary... I guess it would start at time 0 or 1).

The answer they give in the book is a simple algorithm which selects the job with the first deadline, and puts it first, then continues in this way to arrange all jobs.

With that being said, an inversion is when a job i is scheduled before of job j, while the deadline for job j is before the deadline for job i. In the book, they say that flipping the job order of two inverted jobs will always result in a lateness that is no bigger than the original lateness.

In the example I gave, I say that at an arbitrary time, there is a deadline for job j. Two time units later is the deadline for job i. Two time units later, job i (which takes two time units to complete) begins. Right after job i finishes, job j (which takes eight time units to complete, starts). This is clearly an inversion because d(j) < d(i) and start(i) < start(j). The lateness of i is 4 finish(i)-d(i) = 4. The lateness of j is 14, because finish(j)-d(j) = 14. So the total lateness of i+j=18 However, when they are swapped, it appears the total lateness i+j = 24, contradicting the fact that swapping an inversion should never lead to an increase in lateness.

Sorry if this is complex but thanks for your help,

Eric

[egawtry]

Ok, I get it now.

1. Your math is a little off.
2+2 = 4
2+2+8 = 12
Total = 16

Inverted:

2+8 = 10
8+2 = 10
Total = 20

2. I agree, the proof doesn't work.

-Erik