Seminários de Otimização Combinatória e Grafos


Data: 05/03/2010
Horário: 16:00hs
Local: Auditório do Numec
Palestrante: Rafael Crivellari Saliba Schouery
Título: Approximate Mechanism Design Without Money

Resumo: Nesse seminário apresentamos o paper Approximate Mechanism Design Without Money de Procaccia e Tennenholtz. Em muitos cenário da Teoria Algorítimica dos Jogos procuramos desenvolver mecanismos à prova de estratégia, onde o jogador não se beneficia ao mentir. é comum utilizar diversas formas de pagamento financeiro aos jogadores para incentiva-los a dizer a verdade. Mas muitas vezes não é possível ou ético realizar tais pagamentos, um exemplo é a situação onde o governo deseja prover um bem para a sociedade. Procaccia e Tennenholtz mostraram resultados relativos a mecanismos à prova de estratégia sem o uso de dinheiro para os problemas 1-median e 1-center na reta real. Apresentaremos tais mecanismos além das provas de resultados de lowerbounds e upperbounds para a razão de aproximação.


Data: 19/03/2010
Horário: 14:00hs
Local: Auditório do Numec
Palestrante: Raphael Ribas
Título: Uma introdução ao método da discrepância

Resumo: O método da discrepância é um conjunto de técnicas baseadas na teoria da discrepância. Essa teoria se preocupa com a questão de quão bem podemos aproximar um conjunto com um subconjunto do mesmo, em outras palavras, queremos medir a discrepância mínima que um um subconjunto tem em relação ao conjunto todo. Essa questão foi fundamental na derrandomização de alguns algoritmos. Para os algoritmos em questão, geralmente, estamos interessados em escolher um subconjunto dos dados de entrada que sejam representativos o suficiente. Os métodos da discrepância nos permitem encontrar tais conjuntos de forma determinística. Um algoritmo para o problema da árvore geradora mínima que faz uso dessas técnicas será apresentado. O conteúdo desse seminário foi baseado no livro "The discrepancy method" de Bernard Chazelle


Data: 16/04/2010
Horário: 16:00hs
Local: Auditório do Numec
Palestrante: Christian Tjandraatmadja
Título: Métodos gerais de plano-de-corte para problemas de programação linear inteira mista

Resumo: Neste seminário, apresentaremos uma visão geral de métodos de plano-de-corte para programas lineares inteiros mistos. Resolver um problema de programação inteira (pura ou mista) é computacionalmente difícil em geral. Tradicionalmente, para resolvê-lo, enumeramos e resolvemos certos subproblemas com a restrição de integralidade relaxada (ignorada), mas idealmente gostaríamos que eles estivessem o mais próximo possível do problema original. Assim, durante este processo, é útil procurar novas inequações lineares (cortes) que são satisfeitas por todas soluções viáveis do problema original, mas que "cortam fora" soluções viáveis do problema relaxado em que não estamos interessados, aproximando assim o problema relaxado do original. Este método, em geral, contribui bastante para encontrar mais rapidamente uma solução ótima na prática. Descreveremos, para programas inteiros puros, o corte de Chvátal-Gomory, e, para programas inteiros mistos, os cortes inteiro misto de Gomory, de arredondamento inteiro misto, Chvátal-Gomory projetado, de divisão, e de intersecção. Enunciaremos também alguns resultados de equivalência entre classes de corte.


Data: 23/04/2010
Horário: 16:00hs
Local: Auditório do Numec
Palestrante: Rafael da Ponte Barbosa
Título: O problema da cobertura por sensores

Resumo: Considere dada uma área U a ser coberta por um dado conjunto de sensores, cada um com um tempo de duração de bateria e uma área de cobertura (que é uma subárea de U). O chamado Problema da Cobertura por Sensores, em sua versão não-preemptiva, consiste em atribuir a cada sensor um tempo de início (momento em que o sensor deve ser ligado), de modo que a área U fique coberta o maior tempo possível. No caso em que U é um intervalo (caso unidimensional, podendo ser visto, na prática, como uma cerca ou um muro), temos o Problema da Cobertura de Faixa. Buchsbaum e outros [1] provaram que este problema é NP-difícil. Apresentaremos um algoritmo de aproximação de fator constante obtido recentemente por Gibson e Varadarajan [2].
-------------
[1] A.L. Buchsbaum et al., Restricted strip covering and the sensor cover problem. SODA 2007.
[2] M. Gibson e K. R. Varadarajan. Decomposing coverings and the planar sensor cover problem. FOCS 2009.


Data: 21/05/2010
Horário: 16:00hs
Local: Auditório do Numec
Palestrante: Álvaro Junio Pereira Franco
Título: Hierarquias e Planaridade.

Resumo: Este seminário é baseado no artigo "Hierarchies and Planarity Theory" de Di Battista e Nardelli. Neste artigo é dada uma caracterização de hierarquias planares. Pretendemos falar sobre alguns resultados que levaram à tal caracterização.


Data: 11/06/2010
Horário: 16:00hs
Local: Auditório do Numec
Palestrante: Márcio Oshiro
Título:

Resumo:


Free Stuff: Wallpaper - Screensaver - Game - Video - Emoticon - Clipart - Icon - Myspace - Tattoo - Template - Image Hosting

Design downloaded from Free Templates - your source for free web templates