I know this is a very specific question, but: Let's assume that someone designed a 1.1 approximation algorithm for the load balancing problem involving exactly 2 machines. After running the algorithm on a set of n activities, the final loads are 80 for the first machine and 120 for the second one. Is this possible given that:

a) the aforementioned job set only contained jobs with a load less than 100?

b) the aforementioned job set only contained jobs with a load less than 10?

This is taken from a set of exercises given by my uni professor as preparation for the final exam.

  • $\begingroup$ Unclear what you call a "load time". Both statements can be true, take all "load times" equal to $1$. $\endgroup$ May 13 at 16:43
  • $\begingroup$ Yep, I see why it was unclear. I edited the question. Thanks. $\endgroup$
    – asparagus
    May 16 at 12:04
  • 1
    $\begingroup$ @asparagus Please tell us, what you tried by yourself. We want to see some effort. $\endgroup$ May 16 at 12:29
  • $\begingroup$ Please edit the question to make it understandable. $\endgroup$ May 16 at 12:34
  • 1
    $\begingroup$ We're not looking for posts that consist solely of the statement of an exercise-style task. We're happy to help you understand the concepts but just solving exercises for you is unlikely to achieve that. You might find this page helpful in improving your question. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. $\endgroup$
    – D.W.
    May 16 at 16:44


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.