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).