============================================================
   Seminário de Teoria da Computação e Combinatória (TCC)

============================================================

Título:      O problema da localização de instalações com 
             movimentos
            
Palestrante: Orlando Lee
             Instituto de Computação, UNICAMP

Hora e Data: 14h, sexta-feira, 11 de maio de 2012

Local:       Sala Multi-usos do Numec

Resumo: 

O problema da  localização de instalações (Facility Location
Problem) é um problema  bem conhecido. Na sua versão online,
uma requisição (um ponto em  um espaço métrico) chega a cada
instante de tempo e deve-se decidir se

  (i) esta será atendida por uma instalação já aberta 
      anteriormente ou 
 (ii) será aberta uma nova instalação (a um certo custo de
      abertura) para atendê-la.  

Ao  atribuir  uma  instalação  para atender  uma  requisição
paga-se  a  distância entre  ambos  (custo  de conexão).   O
objetivo é minimizar o custo total (de abertura e conexão).

Neste  seminário  discutiremos   uma  variante  do  problema
proposta  por  Divéki  e  Imreh  em que  é  permitido  mover
instalações  previamente  abertas  (atualizando o  custo  de
conexão).  Apresentaremos um algoritmo 2-competitivo (desses
autores) para  esta versão  do problema e  outros resultados
relacionados.

Referência: 

  G. Divéki e C. Imreh, 
  Online facility location with facility movements,
  Central European J. of Operations Research. 
  Volume 19, Number 2 (2011), 191-200.