Carregant...
Carregant...

Vés al contingut (premeu Retorn)

Approximating scheduling problems in parallel

Autor
Serna, M.; Xhafa, F.
Tipus d'activitat
Article en revista
Revista
Lecture notes in computer science
Data de publicació
1997
Volum
1300
Pàgina inicial
440
Pàgina final
449
DOI
https://doi.org/10.1007/BFb0002768 Obrir en finestra nova
URL
https://link.springer.com/chapter/10.1007/BFb0002768 Obrir en finestra nova
Resum
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...
Grup de recerca
ALBCOM - Algorismia, Bioinformàtica, Complexitat i Mètodes Formals

Participants