Pre-requisito: MC448 / MC458

Ementa:

Medidas de perfomance. Algoritmos Combinatórios.  Métodos usando Programação Linear. Método Primal-Dual.  Métodos Probabilísticos.  Programação Semidefinida.  Complexidade de aproximação.

Programa:

1. Aproximação absoluta e suas limitações

    Sugestão: Coloração em grafos planares. Limitações: problema da mochila e clique

    máximo

2. Algoritmos Combinatórios

    Sugestão: Escalonamento de tarefas, Cobertura por vértices, Cobertura por Conjuntos,   

    Caixeiro viajante e Árvore de Steiner

3. Esquemas de aproximação

    Sugestão de exemplos: Problema da Mochila (FPTAS), Problema de Escalonamento de 

    Tarefas (PTAS) e Problema de empacotamento (APTAS)

4. Método de Arredondamento por programação linear

    Sugestão de exemplos: Problemas da cobertura por vértices e cobertura por conjuntos

5. Métodos baseados em dualidade de programas lineares e dual fitting

    Sugestão de exemplos: Problema da cobertura por conjuntos

6. Método primal dual

    Sugestão de exemplos: Problema da transversal mínima, problema de localização de

    recursos, problema da floresta de Steiner

7. Algoritmos aproximados probabilísticos e sua desaleatorização

    Sugestão de exemplos: Arredondamento probabilístico para problema da satisfatibilidade

    máxima e da Cobertura por conjuntos, desaleatorização de algoritmo para o problema da 

    satisfatibilidade máxima

8. Programação Semidefinida

    Sugestão de exemplos: Problema do corte máximo

9. Inaproximabilidade e provas verificáveis probabilisticamente

    Sugestão de exemplos: Inaproximabilidade por redução, classe PCP (Probabilistic  

    Checkable Proofs), inaproximabilidade do Clique por PCP

10. Outros tópicos

Bibliografia:

1. V. Vazirani. Approximation Algorithms, Springer-Verlag (2001).
2. M.H. Carvalho, M.R. Cerioli, R. Dahab, P. Feofiloff, C.G. Fernandes, C.E. Ferreira, K.S. Guimarães, F.K. Miyazawa, J.C. Pina Jr., J. Soares e Y. Wakabayashi. Uma introdução sucinta a algoritmos de aproximação, Editora do IMPA (2001).


3. D.S. Hochbaum (ed). Approximation Algorithms for NP-Hard Problems, PWS Publishing Company (1997).
4. G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchett-Spaccamela e M. Protasi.  Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties, Springer- Verlag (1999).