MAC5727
Algoritmos de Aproximação

Home  |   Administração  |   Livros  |   WWW  |   Diário  |   Tarefas  |   Alunos

 

Apresentação Um algoritmo de aproximação para um problema de otimização é um algoritmo eficiente (polinomial) que produz uma solução com garantia de qualidade, ou seja, uma solução cujo valor não é pior que uma fração pré-determinada do ótimo.  (Assim, um algoritmo de aproximação é mais que uma mera heurística, que não dá qualquer garantia sobre a qualidade da solução.) Considere, por exemplo, o problema de encontrar uma clique máxima num grafo.  Um algoritmo de aproximação típico produz uma clique de tamanho pelo menos 50% do máximo.  Dizemos que um tal algoritmo tem razão de aproximação 2 (pois 2×50% = 100%). Para a grande maioria dos problemas de otimização interessantes não se conhecem algoritmos exatos eficientes.  Para esses problemas os algoritmos de aproximação são muito úteis. Nem todo problema de otimização admite algoritmo de aproximação. Para certos problemas, encontrar uma solução aproximada é tão difícil quanto encontrar uma solução ótima… Livro A principal referência é o livro Uma Introdução Sucinta a Algoritmos de Aproximação de Carvalho, Cerioli, Dahab, Feofiloff, Fernandes, Ferreira, Guimarães, Miyazawa, Pina Jr., Soares, Wakabayashi. Veja detalhes na página de bibliografia.

Conteúdo Recapitulação de resultados básicos sobre grafos, complexidade computacional e probabilidade. Métodos de desenvolvimento de algoritmos de aproximação: métodos métricos, métodos probabilísticos, métodos baseados em programação semidefinida e métodos primais-duais. Algoritmos de aproximação para problemas de escalonamento, de bin packing, de geometria computacional, e problemas de otimização em grafos (coberturas, empacotamentos, conectividade e cortes). Complexidade de aproximações: classes de complexidade Max SNP e APX, reduções, alguns resultados de inaproximabilidade. Pré-requisitos Convém que o aluno tenha alguma noção dos seguintes assuntos: Teoria dos Grafos, Programação Linear, Análise de Algoritmos e Teoria da Complexidade de Computação.

MAC5727 é disciplina de pós-graduação do IME-USP.  Há uma disciplina semelhante no BCC com sigla MAC0450.