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