Uma Introdução Sucinta a Algoritmos de Aproximação

Curso (nível intermediário) no 23º Colóquio Brasileiro de Matemática


Produção realizada e patrocinada pelo projeto PRONEX Complexidade de Estruturas Discretas (Projeto ProNEx 107/97).

    Livro disponível em formato pdf e ps.gz.

Autores Prefácio [pdf] [ps]

Sumário [pdf] [ps]

  1. Introdução
  2. Algoritmos Clássicos
  3. Método Primal
  4. Método Dual
  5. Método Primal-Dual
  6. Algoritmos Probabilísticos
  7. Programação Semidefinida
  8. Inaproximabilidade
Errata [pdf] [ps.gz]

Problemas de otimização têm o objetivo de encontrar um ponto ótimo (mínimo ou máximo) de uma função definida sobre um certo domínio. Os problemas de otimização combinatória têm domínio finito. Embora os elementos do domínio possam, em geral, ser facilmente enumerados, a idéia ingênua de testar todos os elementos na busca pelo melhor mostra-se inviável na prática pois o domínio é tipicamente muito grande.

Como exemplos clássicos de problemas de otimização combinatória podemos citar o problema do caixeiro viajante, o problema da mochila, o problema da cobertura mínima por conjuntos, o problema da floresta de Steiner e o problema da satisfatibilidade máxima. Todos surgem naturalmente em aplicações práticas, tais como o projeto de redes de telecomunicação e de circuitos VLSI, o empacotamento de objetos em containers, a localização de centros distribuidores, o escalonamento e roteamento de veículos, etc. Outras áreas de aplicação incluem a estatística (análise de dados), a economia (matrizes de entrada/saída), a física (estados de energia mínima), a biologia molecular (alinhamento de DNA e proteínas, inferência de padrões), etc.

O desenvolvimento de algoritmos de aproximação surgiu em resposta à dificuldade computacional de muitos dos problemas de otimização combinatória: em termos técnicos, muitos são NP-difíceis. Nessa situação, é razoável sacrificar a otimalidade em troca de uma aproximação de boa qualidade que possa ser eficientemente calculada. Esse compromisso entre perda de otimalidade e ganho em eficiência é o paradigma dos algoritmos de aproximação. Convém observar que um algoritmo de aproximação não é simplesmente uma heurística: ele garante encontrar, eficientemente, um elemento do domínio cujo valor guarda uma relação pré-estabelecida com o valor ótimo.

No início da década de 70, Garey, Graham e Ullman, bem como Johnson, formalizaram o conceito de algoritmo de aproximação. O conceito já estava implícito em um trabalho de Graham sobre um problema de escalonamento em máquinas paralelas e em um trabalho de Erdös sobre grafos bipartidos. Na década de 90, o estudo de algoritmos de aproximação passou a receber um tratamento mais sistemático, com a formalização e o uso de técnicas e ferramentas aplicáveis a toda uma gama de problemas. É importante mencionar também o aparecimento de certos resultados negativos de aproximabilidade: para alguns problemas, aproximar é tão difícil quanto resolver. Em termos mais técnicos, alguns problemas não admitem algoritmos de aproximação com razão melhor que um certo limiar, a menos que P=NP. As teorias nessa direção foram impulsionadas na década de 90 pelas descobertas de Arora et al., que provaram resultados desse tipo para vários problemas usando caracterizações probabilísticas da classe NP.

O desenvolvimento de algoritmos de aproximação e de provas de inaproximabilidade é uma das linhas de pesquisa que mais cresceu ultimamente na área de otimização combinatória e teoria da computação. O objetivo deste livro é apresentar sucintamente uma visão sistemática das técnicas utilizadas no projeto de algoritmos de aproximação e dar uma idéia dos limites intrínsecos da aproximabilidade.

Envie comentários, sugestões ou erros encontrados para aprox@ime.usp.br


Last modified: Wed Oct 21 14:56:40 BRST 2009