Programação das aulas

Agosto

Setembro

Outubro

• 1 de outubro (Aula 14):
  • Arredondamento probabilístico não-uniforme
  • Melhor de dois
  Leitura recomendada: seções 5.4 a 5.5 do WS.
  Transparências: [pdf | ps.gz]

• 3 de outubro (Aula 15):
  • Arredondamento não-linear
  • Arredondamento probabilístico para o PCST
  Leitura recomendada: seções 5.6 e 5.7 do WS.
  Transparências: [pdf | ps.gz]

• 15 de outubro:
  • Segunda Prova
  Matéria da prova: material coberto depois da primeira prova dos capítulos 3, 4 e 5 do WS.

• 17 de outubro (Aula 16):
  • Arredondamento probabilístico para o FLP
  • Revisitando o problema de escalonamento da aula 10
  Leitura recomendada: seções 5.8 e começo da 5.9 do WS.
  Transparências: [pdf | ps.gz]

• 22 de outubro (Aula 17):
  • Escalonamento em uma máquina com pesos, minimizando a soma ponderada dos tempos de conclusão
  • Lista 5
  Leitura recomendada: seções 5.8 do WS.
  Transparências: [pdf | ps.gz]

• 24 de outubro (Aula 18):
  • MAXCUT: uma formulação quadrática e sua relaxação vetorial
  • Algoritmo de Goemans e Williamson
  Leitura recomendada: começo do cap 7 do livro de aproximação.
  Transparências: [pdf | ps.gz]

• 29 de outubro (Aula 19):
  • Análise do algoritmo de Goemans e Williamson para o MAXCUT
  • Programação semidefinida
  • Correlational clustering
  Leitura recomendada: cap 7 do livro de aproximação e seções 6.1, 6.2 e 6.4 do WS.
  Transparências: [pdf | ps.gz]

• 31 de outubro (Aula 20):
  • Método primal-dual: revisão
  • Feedback vertex set problem
  Leitura recomendada: secs 7.1 e 7.2 do WS.
  Transparências: [pdf | ps.gz]