-------------------------------------------------------------------------
     Programação Preliminar do Encontro em Algoritmos de Aproximação

               Itatiaia-RJ,  7-11 de outubro de 2000.


Sábado dia 7 de outubro:

   16:00 - 17:00  Entrada no Hotel.

   17:00 - 18:00  Introdução a Programação Linear e Dualidade
                  Apresentação: Paulo

   18:00 - 19:00  Algoritmos de Aproximação usando métodos por arredondamentos.
                  Apresentação: Carlinhos, Célia, Katia.

   19:00 - 20:00  Algoritmos de Aproximação usando resultados de dualidade.
                  Apresentação: Celina, Cris, Márcia.

   20:00 -        Jantar.


Domingo dia 8 de outubro:

    9:00 - 10:00  Algoritmos de Aproximação usando o método Primal Dual I
                  Fluxo Máximo, Hitting Set, Vertex Cover.
                  Apresentação: Coelho, José, Marcelo.

   10:00 - 10:15  Coffee Break.

   10:15 - 11:15  Algoritmos de Aproximação usando o método Primal Dual II
                  Floresta de Steiner.
                  Apresentação: Cadão, Cid, Flávio, Yoshiko.

   11:15 - 12:15  Algoritmos de Aproximação usando o método Primal Dual III
                  Prize-Collecting.
                  Apresentação: Cris.

   12:15 - 14:00  Almoço.

   14:00 - 15:00  Problema do K-MST.
                  Apresentação: Paulo

   15:00 - 16:00  O Problema de Escalonamento de Tarefas: 
                  um Estudo de Formulações Inteiras e Aproximações 
                  Apresentação: Manoel Campêlo Neto e Ricardo C. Corrêa
                  (ver resumo abaixo)

   16:00 - 16:15  Coffe Break.

   16:15 - 17:30  Propostas de problemas promissores e divisão dos
                  participantes em grupos de estudo.

   17:30 - 19:00  Discussões sobre o texto de algoritmos de aproximação.

   19:00 - 21:00  Jantar.


Segunda-feira dia 9 de outubro:
   
    8:00 - 10:00  Estudos/Discussões dos problemas em grupos.

   10:00 - 10:15  Coffee Break.

   10:15 - 12:00  Estudos/Discussões dos problemas em grupos.

   12:00 - 14:00  Almoço

   14:00 - 16:00  Estudos/Discussões dos problemas em grupos.

   16:00 - 16:15  Coffee Break.

   16:15 - 19:00  Estudos/Discussões dos problemas em grupos.

   19:00 - 21:00  Jantar.


Terça-feira dia 10 de outubro:
      
    8:00 - 10:00  Apresentação de relatorio parcial dos grupos
                  de estudo.

   10:00 - 10:15  Coffee Break.

   10:15 - 12:00  Estudos/Discussões dos problemas em grupos.

   12:00 - 14:00  Almoço

   14:00 - 16:00  Estudos/Discussões dos problemas em grupos.

   16:00 - 16:15  Coffee Break.

   16:15 - 17:00  Estudos/Discussões dos problemas em grupos.

   17:00 - 19:00  Discussões sobre o projeto Pronex, sobre o subgrupo
                  Aprox, próximos passos,...
                  Coordenado pelo Yoshi.

   19:00 - 21:00  Jantar.


Quarta-feira dia 11 de outubro:
      
    8:00 - 10:00  Estudos/Discussões dos problemas em grupos.

   10:00 - 10:15  Coffee Break.

   10:15 - 11:30  Apresentação de relatorio final dos grupos de estudo.

   11:30 - 12:00  Finalização e Saida do hotel

   12:00 - 14:00  Almoço


Obs.: A programação acima pode ter alterações antes e durante o evento.
-----------------------------------------------------------------------------
(*)
             O Problema de Escalonamento de Tarefas: 
         um Estudo de Formulações Inteiras e Aproximações

           Manoel Campêlo Neto e Ricardo C. Corrêea 
                Universidade Federal do Ceará

Muitos algoritmos largamente empregados em aplicações científicas e
industriais apresentam a propriedade de poderem ser descritos em
termos de um conjunto de tarefas a serem executadas respeitando uma
certa relação de ordem parcial sobre elas. O problema que será o tema
deste seminário consiste a, dado um sistema a múltiplos processadores,
encontrar uma atribuição das tarefas de um algoritmo dado aos
processadores de tal forma a minimizar o tempo de execução do
algoritmo. Supõe-se que os processadores são idênticos e totalmente
interligados por canais de comunicação capazes de transportar
mensagens entre quaisquer dois processadores.

O problema introduzido acima, chamado de escalonamento de tarefas a
múltiplos processadores (MSP), tem sido intensamente estudado por
diversos pesquisadores. Dentre a grande variedade de algoritmos
propostos na literatura, uma abordagem baseada na solução ralaxada de
um problema de programação inteira surgiu recentemente como uma
alternativa para a obtenção de soluções aproximadas. Este seminário
consistirá na apresentação dos resultados relativos a formulações do
MSP como problema de programação inteira e suas relações com
algoritmos de aproximação.