Programação das aulas de MAC5711

Primeiro semestre de 1999

Primeira parte do cronograma

Mês de Abril (cont)

• 26 de abril (aula 11):
  • Métodos Probabilísticos: MAXCUT
  Leitura recomendada: lectures 4 e 5 das notas do Williamson.
• 28 de abril (aula 12):
  • Métodos Probabilísticos: MAXSAT
  Leitura recomendada: lectures 4 e 5 das notas do Williamson.
  • Prova 1
  Matéria da prova: métodos baseados em LP (métodos de arredondamento, primais-duais, métricos, etc) e divisão e conquista.

• 3 de maio (aula 13):
  • Métodos Probabilísticos: MAXSAT usando programação linear
  • Lista 4 [ps | tex | pdf]
• 5, 10, 12, 17, 19 de maio
• 24 de maio (aula 14)
  • Programação Semidefinida: MAXCUT
  Leitura recomendada: partes de M. Goemans and D. Williamson, Improved Approximation Algorithms for Maximum Cut and Satisfability Problems using Semidefinite Programming
• 26 de maio (aula 15)
  • Programação Semidefinida
• 31 de maio (aula 16)
  • Programação Semidefinida para MAX2SAT
  • 0.755-aproximação para MAXSAT

• 2 de junho (aula 17)
  • Inaproximabilidade do TSP
  Leitura recomendada: capítulo 3 do Vazirani
• 7 de junho (aula 18)
  • TSP métrico: uma 2-aproximação e o algoritmo de Christofides
  • PTAS e FPTAS
  • um algoritmo pseudo-polinomial para o Knapsack
  Leitura recomendada: cápitulo 8 do Vazirani
• 9 de junho (aula 19)
  • FPTAS para o Knapsack
  • Bin Packing e Minimum Makespan Scheduling
  Leitura recomendada: seção 6 das notas do Goemans
• 14 de junho (aula 20)
  • 2-aproximação para o minimum makespan scheduling
  • Bin Packing com um número fixo de tamanhos para os objetos
  • Lista 5 [ps | tex | pdf]
  Leitura recomendada: capítulo 9 do Vazirani
• 16 de junho (aula 21)
  • PTAS para minimum makespan scheduling
  • Resultados de inaproximabilidade
  Leitura recomendada: livro do Zé Augusto e do Yoshi
• 21 de junho (aula 22)
  • L-reduções e a classe Max SNP-difícil de problemas
  Leitura recomendada: livro do Zé Augusto e do Yoshi