Workshop em Algoritmos de Aproxima��o

Patrocinado pelo Projeto ProNEx "Complexity of Discrete Structures"

Data: 7 a 11 de outubro de 2000

Local: Itatiaia

Organiza��o

O evento ter� duas fases. Na primeira fase ser�o discutidas t�cnicas de desenvolvimento de algoritmos de aproxima��o e resultados b�sicos, com o objetivo de formarmos uma base comum m�nima inicial de conhecimento na �rea. Nos concentraremos em t�cnicas derivadas de programa��o linear. Para esta fase, est� sendo preparado um texto que conter� alguns t�picos escolhidos. Mais tarde este texto dever� se tornar um livro sobre algoritmos de aproxima��o. Na segunda fase, nos concentraremos em problemas e/ou artigos espec�ficos. Al�m disso, durante o evento discutiremos o formato do texto que est� sendo preparado.

Programa do evento

Lista de discuss�o

Temos uma lista de discuss�o. Para ter o seu e-mail incluido na lista, escreva para fkm@ic.unicamp.br. Para enviar um e-mail para a lista, escreva para keidi-aprox@ime.usp.br.

Texto sobre algoritmos de aproxima��o

Os seguintes cap�tulos foram preparados para esta primeira vers�o do texto.
  1. Programa��o Linear: cont�m um resumo dos conceitos necess�rios para a compreens�o dos m�todos de desenvolvimento de algoritmos de aproxima��o baseados em programa��o linear. Respons�vel: Paulo.
  2. M�todo de Arredondamento: cont�m a descri��o e alguns exemplos de aplica��o do m�todo de arredondamento. Respons�veis: Carlinhos, C�lia e K�tia.
  3. M�todo Dual: cont�m a descri��o e alguns exemplos de aplica��o do chamado m�todo dual para algoritmos de aproxima��o. Respons�veis: Celina, Cris e M�rcia.
  4. M�todo Primal-Dual para Algoritmos de Aproxima��o: cont�m uma introdu��o ao m�todo primal-dual para algoritmos de aproxima��o, incluindo a sua aplica��o ao hitting-set problem. Respons�veis: Coelho, Marcelo e Z� Augusto.
  5. M�todo Primal-Dual para o Problema da Floresta de Steiner: descreve uma variante mais sofisticada do m�todo primal-dual. Respons�veis: Cad�o, Cid, Fl�vio e Yoshiko.
  6. M�todo Primal-Dual para Problemas com Penalidades: descreve mais uma variante do m�todo primal-dual. Respons�vel: Cris.

Os cap�tulos est�o escritos em estilos bem diferentes. Pretendemos durante o evento discutir qual o estilo mais adequado para o texto final.

Pedimos ent�o que todos os participantes tentem ler o maior n�mero de cap�tulos poss�vel e opinem sobre a nota��o, a ordem de exposi��o, enfim, s�o bem-vindos quaisquer coment�rios que possam tornar o texto melhor.

Cap�tulos dispon�veis

Traga material! Por exemplo, traga com voc� artigos de problemas em que voc� gostaria de testar a aplica��o de alguns destes m�todos.

Bibliografia b�sica

Aqui se encontra uma parte da bibliografia usada durante a escrita dos cap�tulos.

Local do evento

O workshop acontecer� no Hotel Simon em Itatiaia. O Hotel Simon fica na rodovia BR 485 Km 12, em Itatiaia. Esta rodovia � a Estrada do Parque Nacional. O acesso ao hotel � pela Rodovia Presidente Dutra Km 318 (trevo de acesso � Itatiaia). (Distancias de Resende = 25 Km, do Rio = 166 Km e de S�o Paulo = 270 Km.)

O Hotel fica dentro do parque. Aqueles que v�o de �nibus podem descer em Itatiaia ou Resende. De Itatiaia podem pegar um t�xi ou �nibus que entram no parque saindo nos hor�rios: 2:40 e 5:20 da tarde. O telefone do hotel, caso haja algum problema, � (24) 352-1122.


Last modified: Tue Oct 31 13:59:57 BRDT 2000