Programação das aulas

Agosto

Setembro

Outubro

Novembro

• 5 de novembro (Aula 21):
  • Primal-dual: caminho mais curto
  • Floresta de Steiner
  • Lista 6
  Leitura recomendada: seções 7.3 e parte da 7.4 do WS e parte da sec 5.4 do livro de aproximação.
  Transparências: [pdf | ps.gz]

• 7 de novembro (Aula 22):
  • Floresta de Steiner: continuação da análise
  • Primal-dual para Localização de Facilidades
  Leitura recomendada: sec 7.4, sec 5.4 do livro de aproximação e começo da sec 7.6 do WS.
  Transparências: [pdf | ps.gz]

• 12 e 14 de novembro:
  • Semana de break

• 19 de novembro: ponto facultativo

• 21 de novembro (Aula 23):
  • Primal-dual para Localização de Facilidades: análise
  • Inaproximabilidade: L-reduções
  Leitura recomendada: seções 7.6, 16.1 e 16.2 do WS.
  Transparências: [pdf | ps.gz]

• 26 de novembro:
  • Terceira prova
  Matéria da prova: material coberto depois da segunda prova dos capítulos 5, 6 e 7 do WS, cap 7 do livro de aproximação.

• 28 de novembro (Aula 24):
  • Inaproximabilidade: PCP e Unique Games
  Leitura recomendada: seções 16.3 e 16.5 do WS.
  Transparências: [pdf | ps.gz]