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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- M. Goemans, Approximation algorithms, 1994. (notas de aula)
- M. Goemans, and D. Williamson, Improved Approximation Algorithms for Maximum Cut and Satisfability Problems using Semidefinite
Programming, JACM, 42:1115-1145, 1995.
- D. Hochbaum (ed.),
Approximation
Algorithms for NP-hard problems, PWS Publishing Company, 1997.
- V. Vazirani,
Approximation
Algorithms, preprint, 1999.
- D. Williamson,
Lecture Notes
on Approximation Algorithms, Fall 1998.
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