Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I have the following problem:

We have a set of tasks that requires some preprocessing time. When the job is preprocessed, the job can be executed on a parallel thread that also requires some time. The preprocessing can only be done on a single thread and cannot be multi-threaded.

My task was to give a greedy algorithm that determines a schedule that minimizes the latest end time. I thought this could be accomplished with a schedule that schedules jobs according to their parallel processing time (the ones with the longest parallel processing time first).

Now I have to prove that this algorithm works by giving an exchange argument. I've read the book but I'm not sure on where to start (I'm very bad in proving things). Suppose that we have an optimal schedule S. When using an exchange argument, I have to transform this optimal schedule to the greedy one that my algorithm returns.

Could anyone please give me a hand?


share|cite|improve this question

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.