Loading...
Loading...

Go to the content (press return)

Approximating scheduling problems in parallel

Author
Serna, M.; Xhafa, F.
Type of activity
Journal article
Journal
Lecture notes in computer science
Date of publication
1997
Volume
1300
First page
440
Last page
449
DOI
https://doi.org/10.1007/BFb0002768 Open in new window
URL
https://link.springer.com/chapter/10.1007/BFb0002768 Open in new window
Abstract
We show how to approximate in NC the problem of Scheduling Unrelated Parallel Machines, for a fixed number of machines. We develop a (2 + e)-approximate parallel algorithm for the problem. Our approach shows how to relate the linear program obtained by relaxing the integer programming formulation of the problem with a linear program formulation that is positive and in the packing/covering form. The relationship established enables us to transfer approximate fractional solutions from the later fo...
Group of research
ALBCOM - Algorithms, Computational Biology, Complexity and Formal Methods

Participants