MAC 5727 / MAC0450 -- Algoritmos de Aproximação

1o. Semestre de 2008

Material básico

1. Livro-texto: Uma introdução sucinta a algoritmos aproximação
2. Approximation Algorithms and Combinatorial Optimization (eds. P. Crescenzi, V. Kann), A list of NP-complete optimization problems
   
3. M. Goemans, Approximation algorithms, 1994. (notas de aula)
4. D. Hochbaum (ed.), Approximation Algorithms for NP-hard problems, PWS Publishing Company, 1997.
5. R. Motwani, Lectures Notes on Approximation Algorithms
6. V. Vazirani, Approximation Algorithms Informações sobre o livro
7. D. Williamson, Lecture Notes on Approximation Algorithms, Fall 1998.
8. Problemas em P, em NP e a questão "P versus NP"

Outros textos

1. Como escrever "provas matemáticas" [Veja] (disponível no BIME)
2. Como escrever textos matemáticos [Veja]

Exercícios

• Lista 1
• Lista 2
• Lista 3
• Lista 4
• Lista 5
• Lista 6
• Lista 7 - leitura de artigos
  • David Karger and Cliford Stein, A New approach to the Minimum Cut Problem
• Lista 8 - leitura de artigos
  • J.A. Hoogeveen, Analysis of Christofides' heuristic: some paths are mor more difficult than cycles
  • C. Chekuri and M. Pál, An O(log n)-approximation ratio for the asymetric traveling salesman path problem

Avaliação do aprendizado do aluno

Será feita levando em conta as seguintes atividades:
• Listas de exercícios (entrega obrigatória)
• Provas (final de abril e meados de junho)
• Um seminário sobre um tópico a ser escolhido no final do semestre

Aulas

1. 04/março - Introdução
   • Uma visão geral dos tópicos que serão cobertos nesta disciplina (requisitos, textos, material disponível)
   • Cap.1 Introdução (definições básicas e notação)
2. 06/março
   • Cap.2 Algoritmos Clássicos (2.1. Escalonamento; Cobertura por conjuntos - introdução)
3. 11/março
   • Cap.2 Algoritmos Clássicos
     • 2.2. Cobertura por Conjuntos (set cover) - relação com os problemas em grafos sobre cobertura de arestas por vértices e cobertura de vértices por arestas, hipergrafos
     • Corte Multiseparador Mínimo - introdução
4. 13/março
   • Cap.2 Algoritmos Clássicos (material não apresentado no livro-texto)
     • II.3 Corte Multiseparador Mínimo (multiway cut) [algoritmo guloso] -- (notas de aula)
       
     • II.4 Caminhos Disjuntos nas Arestas [algoritmo guloso] -- (notas de aula)
5. 25/março
   • Cap.2 Algoritmos Clássicos
     • TSP - O Problema do Caixeiro Viajante
6. 27/março
   • Cap.3 Método Primal
     • Técnica do arredondamento
     • Técnica métrica
7. 01/abril
   • Cap.3 Método Primal
     • Técnica métrica (Problema MinMCut)
8. 03/abril
   • Cap.4 Método Dual
     • Método Dual simples e Dual Maximal

   (LATIN 2008 + Semana do Break)

9. 22/abril
   • Cap.5 Método Primal-Dual
     • O Método Primal Dual Clássico (para achar solução exata)
     • Método de Aproximação Primal-Dual
10. 24/abril
    • Cap.5 Método Primal-Dual
      • Problema da Transversal Mínima
11. 29/abril
    • Cap.5 Método Primal-Dual
      • Problema da Floresta de Steiner
12. 06/maio
    • Cap.5 Método Primal Dual
      • Problema da Localização de recursos ( Facility Location Problem)
13. 08/maio
    • Cap.6 Algoritmos Probabilísticos
      • Algoritmos para o MAX-3SAT
14. 13/maio
    • 1a. Prova
15. 15/maio
    • Cap.6 Algoritmos Probabilísticos
      • Problema do Multicorte Mínimo (MinMcut)
16. 20/maio
    • Cap.6 Algoritmos Probabilísticos
      • Desaleatorização - método das esperanças condicionadas
17. 27/maio
    • Cap.7 Programação Semidefinida
      • O problema do corte máximo (algoritmo probabilístico de Goemans-Williamson)
18. 03/junho
    • Cap.7 Programação Semidefinida
      • O problema do Max2SAT
19. 05/junho
    • Cap.8 Inaproximabilidade
20. 10/junho
    • Cap.8 Inaproximabilidade
21. 12/junho
    • Apresentação dos alunos
22. 17/junho
    • Apresentação dos alunos
23. 19/junho
    • Apresentação dos alunos

Last modified: Tue Feb 10 19:54:11 BRST 2009