Familiarizar os alunos com as técnicas de desenvolvimento e análise de algoritmos de aproximação para problemas combinatórios e com os resultados da teoria de complexidade relacionados a aproximações. São estudados algoritmos de aproximação para vários problemas, dentre os quais destacamos problemas de escalonamento, bin packing, otimização sobre grafos (TSP métrico, cobertura, corte máximo e outros), max-3SAT, reduções que preservam aproximação, e inaproximabilidade.
- Docente: Gabriel Morete de Azevedo
- Docente: Yoshiko Wakabayashi