Departamento de Ciência da Computação  |  Instituto de Matemática e Estatística  |  USP

MAC5727
Algoritmos de Aproximação

ano 2003

Home  |   Administração  |   Fórum  |   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

  1. Recapitulação de resultados básicos sobre grafos, complexidade computacional e probabilidade.
  2. 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.
  3. 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).
  4. 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:



Lista de problemas

  • Escalonamento de tarefas (task scheduling)
  • Caixeiro viajante métrico (metric traveling salesman, metric TSP)
  • Mochila (knapsack)
  • Cobertura por conjuntos (set cover)
  • Cobertura por vértices (set cover)
  • Multicorte mínimo (minimum multicut)
  • Corte máximo (Max-Cut)
  • Floresta de Steiner (Steiner forest)
  • Satisfatibilidade máxima (Max-Sat)

Métodos e algoritmos

  • Método primal, método dual, método primal-dual
  • Algoritmos probabilísticos e desaleatorização (derandomization)
  • Programação semidefinida (semidefinite programming)
  • Algoritmo de Graham para escalonamento
  • Algoritmo de Ibara e Kim para o problema da mochila
  • Algoritmo de Christofides para o TSP métrico
  • Algoritmo de Chvátal para cobertura por conjuntos
  • Algoritmo de Hochbaum para cobertura por conjuntos
  • Algoritmo de Garg-Vazirani-Yannakakis para multicorte mínimo
  • Algoritmo de Goemans-Williamson para o problema da floresta de Steiner
  • Algoritmo de Johnson para satisfatibilidade máxima
  • Algoritmo de Goemans-Williamson para satisfatibilidade máxima
  • Algoritmo de Goemans-Williamson para o problema do corte máximo

Inaproximabilidade

  • NP-completude e inaproximabilidade
  • Inaproximabilidade de problemas NP-difíceis
  • Classes de inaproximabilidade
  • Limiares de aproximação

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


Valid CSS! Valid HTML 4.0 URL of this page: http://www.ime.usp.br/~pf/mac5727-2003/
Last modified: Wed Sep 27 13:02:40 BRT 2017
Paulo Feofiloff
DCC  |  IME  |  USP

 

Outros assuntos:
Análise de Algoritmos  |  Minicurso de Análise de Algoritmos  |  Algoritmos de Programação Linear  |  Uma Introdução Sucinta à Teoria dos Grafos  |  Exercícios de Teoria dos Grafos  |  Fluxo em Redes |  Digrafos |  Algoritmos em Grafos com Stanford GraphBase  |  Algoritmos para Grafos via Sedgewick  |  Projeto de Algoritmos em C  |  Estruturas de Dados  |  Literate Programming & CWEB  |  O que é uma prova?  |  Opiniões e notícias