MAC 5727 e MAC 0450 - Algoritmos de Aproximação

2o. Semestre de 2006

Material básico [em construção]

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

1. Capítulo 2: [Lista1.ps] --- [Lista2.ps] --- [Lista3.ps | Lista3.pdf]
2. Capítulo 3 e Capítulo 4: [Lista4.ps | Lista4.pdf]
3. Capítulo 5: Exercícios 5.8 e 5.9 do livro-texto (páginas 57 e 58)
4. Capítulo 6: Exercícios 6.1, 6.2 e 6.4 do livro-texto (páginas 72 e 73)
5. Capítulo 7: Exercício 7.7 do livro-texto (página 84)
6. Capítulo 8:

AVISO IMPORTANTE

1. Condição necessária (não necessariamente suficiente) para aprovação: entregar uma alta porcentagem dos exercícios das listas.

Aulas

1. 07/ago/06 - Introdução
   • Cap.1 Introdução (definições básicas e notação)
   • Cap.2 Algoritmos Clássicos
     • 2.1 Escalonamento (scheduling)
2. 09/ago/06
   • Cap.2 Algoritmos Clássicos
     • 2.1 Escalonamento [algoritmo guloso]
     • 2.2 Cobertura por Conjuntos (MinCC)(set cover) [algoritmo guloso]
3. 14/ago/06
   • Cap.2 Algoritmos Clássicos (não estão no livro)
     • II.3 Corte Multiseparador Mínimo (multiway cut) [algoritmo guloso] --
       [notas de aula preparadas por Fábio Tisovec -- a serem disponibilizadas em breve]
     • II.4 Caminhos Disjuntos nas Arestas [algoritmo guloso] --
       notas de aula preparadas por Cristiane Sato [pdf | ps]
4. 16/ago/06
   • Cap.2 Algoritmos Clássicos (não está no livro) Técnica baseada em melhoria local ( local improvement)
     • II.5 Max Folha Árvore Geradora (MaxFAG)( Maximum-leaf spanning tree )
       [notas de aula preparadas por todos]
5. 21/ago/06
   • Cap.2 Algoritmos Clássicos
     • 2.4 Caixeiro Viajante (TSP - Traveling Salesman Problem)
6. 23/ago/06
   • Cap.3 Método Primal
     • 3.1 Cobertura por Conjuntos
     • III.2 Cobertura (de arestas) por vértices (MinCV)
7. 28/ago/06
   • Cap.3 Método Primal (cont.)
     • 3.2 - MinMCut - Técnica métrica
     • PL "grande"/ problema da separação
8. 30/ago/06
   • Cap.4 Método Dual
     • 4.1 - MinCV (técnica padrão, uso de dualidade)
     • IV.2 - MinCC - técnica da ¨acomodação dual¨ (´dual fitting´)
       [notas de aula preparadas por Karla R.P. do Nascimento -- a serem disponibilizadas em breve]
   • Lista 4 (exercícios para casa)- veja acima no item Exercícios.

   ----- 4 a 9/set/06 -- Semana da Pátria -- feriado escolar -----

9. 11/set/06
   • Cap.5 Método Primal-Dual (cont.)
     • 5.1 - Método primal-dual clássico
     • 5.2 - Metodo de aproximação primal-dual
10. 13/set/06
    • Cap.5 Método Primal-Dual (cont.)
      • 5.3 - Problema da Tranversal Mínima (MinTC)
11. 18/set/06
    • Cap.5 Método Primal-Dual (cont.)
      • 5.4 - Problema da Floresta de Steiner (MinFS) (Aula de Rafael Pereira Luna)
12. 20/set/06
    • Cap.5 Método Primal-Dual (cont.)
      • 5.4 - Problema da Floresta de Steiner. Aspectos relativos à implementação do algoritmo de Goemans e Williamson; discussão sobre a implementação de outros algoritmos (aula de Rafael Pereira Luna).
13. 25/set/06
    • Cap.6 Algoritmos Probabilísticos - algoritmos para MaxSat.
14. 27/set/06
    • Cap.6 Algoritmos Probabilísticos - algoritmos para MaxSat. Desaleatorização. [Tem material das transparências]
15. 2/out/06
    • Cap.6 Algoritmos Probabilísticos - algoritmos para MaxSat.
      • VI.1 Algoritmo probabilístico para o MinMCut(problema do Multicorte Mínimo). Notas de aula a serem preparadas por Mário Leston.
      • VI.2 Algoritmo probabilístico para o MinCC - Exercício: notas de aula a serem preparadas por Leonardo Facci.
16. 4/out/06
    • Cap.7 Programação Semidefinida - Problema do Corte Máximo (MaxCut). Algoritmo de Goemans-Williamson.

    ----- 9 a 11/out -- Semana do break -----

17. 16/out/06
    • Cap.7 Programação Semidefinida
      • Programa quadrático (inteiro), programa quadrático estrito, programa vetorial, programa semidefinido.
      • Problema Max2Sat - um algoritmo (probabilístico) usando programação semidefinida [notas de aula a serem preparadas por Lucas Gadani].
18. 18/out/06
    • Cap.8 Inaproximabilidade
      • Classes de problemas de otimização (relativos à aproximabilidade): PO, FPTAS, PTAS, APX, NPO
      • Problema da Mochila: ilustração de um FPTAS
19. 23/out/06
    • Cap.8 Inaproximabilidade (cont.)
      • 8.2 NP-completude e inaproximabilidade.
      • 8.3 Completude para problemas de otimização - AP-redução
20. 25/out/06
    • Cap.8 Inaproximabilidade O Teorema PCP e prova de que "MaxClique não admite um PTAS, a menos que P = NP". Exemplo de AP-redução (redução de MAx3SAT para MaxClique).
21. 30/out/06
    • Apresentação de Seminários

22. 1/nov/06
    • Apresentação de Seminários

23. 6/nov/06
    • Apresentação de Seminários

24. 8/nov/06
    • Apresentação de Seminários

25. 13/nov/06
    • Apresentação de Seminários

Last modified: Wed Oct 18 22:27:48 -0300 2006