[obm-l] Algoritmo de Graham

[Claudio Buffara <claudio.buffara@xxxxxxxxxxxx>]

Oi, Pessoal:

O Domingos Jr. me falou de um problema interessante, envolvendo o algoritmo
de Graham para "scheduling" (qual a palavra em portugues?):

Suponha que vc tem m máquinas idênticas e n tarefas (cujo tempo de execução
está num vetor v[1..n] de reais positivos).
O algoritmo de Graham é assim:
- ordene v de forma decrescente (v(1) >= v(2) >= ... >= v(n));
- na i-ésima (1 <= i <= n) iteração aloque a i-ésima tarefa na máquina mais
livre (aquela cuja soma dos respectivos v(k)'s é a menor de todas)
(se há empate coloque na máquina de índice menor, por exemplo).
 
Mostre que o algoritmo acima sempre dá uma solução cujo tempo de execução é
no máximo igual a 4/3 do ótimo.
 
Um abraco,
Claudio.

=========================================================================
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
=========================================================================