Please help transcribe this video using our simple transcription tool. You need to be logged in to do so.


The goal of this paper is to study how limited cooperation can impact the quality of the schedule obtained by multiple independent organizations in a typical grid computing platform. This relaxed version of the problem known as the MultiOrganization Scheduling Problem (MOSP) models an environment where organizations providing both resources and jobs tolerate a bounded degradation on the makespan of their own jobs in order to minimize the makespan over the entire platform. More precisely, the technical contributions are the following. First, we improve the existing inapproximation bounds for this problem proving that what was previously though as not polynomially approximable (unless P = NP) is actually not approximable at all. We achieve this using two families of instances whose Pareto optimal solutions are on par with the previous inaproximability bounds. Then, we present two algorithms that solve the problem with approximation ratios of (2; 3/2) and (3; 4/3) respectively. This means that when using the ?rst (second) algorithm, if an organization tolerates that the completion time of its last job cannot exceed twice (three times) the time it would have obtained by itself, then the algorithm provides a solution that is a 3/2- approximation (4/3-approximation) for the optimal global makespan. Both algorithms are ef?cient since their performance ratio correspond to the Pareto optimal solutions of the previously de?ned instances.

Questions and Answers

You need to be logged in to be able to post here.