MO418A/MC748A — Algoritmos de Aproximação

Segundo Semestre de 2019

Aulas: Lehilton Pedrosa

Planilha de notas

Avisos

• 28/11/2019 Enviem a lista 3 até o dia 6/12.
• 28/11/2019 Conjunto independent máximo em grafos planares (Mayara e Welverton).
• 26/11/2019 Shortest superstring (Elisa e Irina).
• 21/11/2019 Dual-fitting para UFLP (Cristina e Miguel).
• 19/11/2019 Escalonamento em máquinas não relacionadas (Marco Antônio).
• 14/11/2019 Unique Games Conjecture (Felipe, Victor e Vinicius ).
• 12/11/2019 Não haverá atividades.
• 07/11/2019 Aula para dúvidas.
• 05/11/2019 Reduções via teorema do PCP.
• 31/10/2019 Reduções que preservam fator.
• 29/10/2019 Reduções de problemas NP-completos.
• 24/10/2019 Primal dual para shortest path e Steiner generalizado (cont).
• 22/10/2019 Primal dual para shortest path e Steiner generalizado.
• 17/10/2019 Revisão do primal-dual e feedback vertex set.
• 16/10/2019 Lista 2.
• 15/10/2019 Semidefinite programming (cont). (exercícios)
• 10/10/2019 Semidefinite programming.
• 08/10/2019 Instruções para seminários.
• 08/10/2019 Parte 11 - Chernoff bounds. (exercícios)
• 01/10/2019 Parte 10 - Arredondamento aleatorizado de PL. (exercícios)
• 26/09/2019 Parte 9 - Algoritmos aleatorizados e MAXSAT. (exercícios)
• 19/09/2019 Parte 8 - Arredondamento determinístido (cont). (exercícios)
• 17/9/2019 Parte 7 - Arredondamento determinístico e método dos elipsoides (cont). (exercícios)
• 12/9/2019 Parte 6 - Arredondamento determinístico e método dos elipsoides.
• 10/9/2019 Introdução a funções submodulares.
• 8/9/2019 De 8 a 19/9 estarei viajando. Os alunos de doutorado Marcelo e Hugo disponibilizaram-se a apresentar parte do capítulo 4, a que voltarei apenas brevemente. A presença não é obrigatória, mas eles poderão ajudar com alguns dos exercícios sugeridos.
• 5/9/2019 Não haverá aula. Transformem a programação dinâmica exponencial para escalonamento visto em sala em um algoritmo polinomial que considera tarefas com tempo arredondado; leiam as notas de aula disponibilizadas e o capítulo do livro.
• 3/9/2019 Lista 1.
• 3/9/2019 Parte 5 - Arredondamento de dados. (exercícios)
• 15/8/2019 Parte 4 - Busca local. (exercícios)
• 15/8/2019 Parte 3 - Algoritmos gulosos. (exercícios)
• 13/8/2019 Parte 2 - Limitantes e programação linear. (exercícios)
• 1º/8/2019 Parte 1 - Introdução a Algoritmos de Aproximação e revisão de complexidade. (exercícios)
• 15/7/2019 Plano de desenvolvimento da disciplina.