Programação das aulas de Algoritmos de Aproximação

Segundo semestre de 2001

• 22 de setembro (aula 4):
  • Técnica do Arredondamento (seção 3.1)
  • Método Dual (capítulo 4)
• 24 de setembro (aula 5):
  • Aplicação do Problema da Cobertura por Conjuntos ao Problema da Supercadeia Mínima (seção 2.3 do livro do Vazirani)
  • Análise do Algoritmo de Chvátal para Cobertura por Conjuntos por meio de programação linear (seção 13.1 do livro do Vazirani)
• 25 de setembro (aula 6)
  • 4-aproximação para o Problema da Supercadeia Mínima (capítulo 7 do Vazirani)

Lista 2: exercícios 3.2 e 4.4 do livro do Colóquio e 2.16 do livro do Vazirani (acho que ele tem número 2.14 na cópia que o Marcelo tem do livro).
A lista deve ser entregue na aula do dia 22/10.

Bônus na Lista 1: primeira parte do exercício 2.11, ou seja, o caso em que queremos um caminho arbitrário, sem pontas pré-determinadas.
Esse exercício deve ser escrito em grupo, no capricho, e valerá 1.5 na nota da Lista 1.

Mês de Agosto

• 11 de agosto (aula 1):
  • Algoritmo de Graham para o Problema do Escalonamento (seção 2.1)
  • Terminologia básica (capítulo 1)
• 13 de agosto (aula 2):
  • Algoritmo de Chvátal para Cobertura por Conjuntos (seção 2.2)
  • Algoritmo de Ibarra e Kim para o Problema da Mochila (seção 2.3)
• 14 de agosto (aula 3)
  • 2-aproximação para o TSP (seção 2.4)
  • Algoritmo de Christofides para o TSP (seção 2.4)

Lista 1: exercícios 2.1, 2.4, 2.8 e 2.11 para o caso em que apenas o início do caminho é dado (o vértice s).
A lista deve ser entregue na aula do dia 22/9.

Alternativamente, o aluno pode entregar uma implementação em C dos algoritmos de Graham, de Chvátal e de Ibarra e Kim. A implementação, além da solução produzida, deve imprimir a melhor delimitação detectada durante o algoritmo (dentre as usadas na prova da razão de aproximação vista em aula).