Programação das aulas

Agosto

• 6 de agosto (Aula 1):
  • Informações gerais e introdução
  • Problema da cobertura por conjuntos
  • Formulação como PLI
  • Arredondamento determinístico (usando uma relaxação linear do PLI)
  Transparências [pdf] [ps.gz]

• 8 de agosto (Aula 2):
  • Breve recaptulação de PL o problema da cobertura por conjuntos
  • Arredondamento de solução dual
  • Algoritmo Primal-Dual
  • Algoritmo Guloso
  Transparências [pdf] [ps.gz]
  Leitura recomendada: cap 1 do WS.

• 13 de agosto (Aula 3):
  • Algoritmo Guloso para o set cover
  • Análise pelo método dual-fitting
  • Lista 1
  Transparências [pdf] [ps.gz].
  Leitura recomendada: cap 1 do WS.

• 15 de agosto (Aula 4):
  • Arredondamento probabilístico
  • Algoritmos gulosos: escalonamento com deadlines em uma máquina
  Leitura recomendada: fim do cap 1 e sec 2.1 do WS.
  Transparências: [pdf] [ps.gz]

• 20 de agosto (Aula 5):
  • Algoritmos gulosos
  • Problema dos k-centros
  • Algoritmo de Graham
  • Algoritmo de Rosenkrantz-Stearn-Lewis para o TSP métrico
  Leitura recomendada: seções 2.2 do WS.
  Transparências: [pdf | ps.gz]

• 22 de agosto (Aula 6):
  • Algoritmos de busca local
  • Escalonamento em máquinas idênticas
  • Corte máximo
  • TSP métrico: mais dois algoritmos
  Leitura recomendada: seções 2.3 e 2.4 do WS, e notas de aula acessíveis aqui.
  Transparências: [pdf | ps.gz]

• 27 de agosto (Aula 7):
  • Arredondamento e programação dinâmica
  • Problema da mochila
  • Escalonamento em máquinas idênticas
  • Lista 2 - exercícios do cap 2 do WS
  Leitura recomendada: sec 3.1 e começo da 3.2 do WS.
  Transparências: [pdf | ps.gz]

• 29 de agosto (Aula 8):
  • PTAS para escalonamento em máquinas idênticas
  Leitura recomendada: sec 3.2 do WS.
  Transparências: [pdf | ps.gz]