Seminário de Otimização - Combinatória


       Algoritmo Primal-Dual 3-aproximado para o
     Problema de Localizacao de Facilidades ( FLP )


           Luis Augusto Angelotti Meira

         Sexta-feira, 6 de setembro de 2002
              Sala 96 (IC2), 13:00hs

Sumário:

 O semina`rio se concentrara` em trazer um histo`rico e motivacao
 do FLP, como modela-lo usando PL, uma breve introducao a
 algoritmos aproximados, e, finalmente um estudo do trabalho de
 Jain e Vazirani que fizeram um algoritmo 3-aproximado com
 complexidade O(m log m ) para o FLP utilizando uma modelagem
 Primal-Dual.


 O problema de localizacao de facilidades ( FLP ) tem a seguinte descricao:
 Dado um conjunto de cidades C, um conjunto de facilidades F, um custo
 f_i para abrir cada i pertencente a F e um custo c_ij para cada
 j pertencente a C ser ligado a uma facilidade aberta i pertencente a F,  encontre um subconjunto
 S em F que minimize Sum(f_i), i aberta + Sum(c_ij), j conectada a i,
 de forma que todas as cidades sejam atendidas.

 Trata-se de um problema cla`ssico, com diversas aplicacoes pra`ticas em redes
 de computadores, que tem sido estudado atrave`s de diversas abordagens,
 desde resolucoes exatas, para instancias pequenas, ate euristicas e,
 recentemente, algoritmos aproximados.


 O me`todo que sera` abordado no semina`rio sera` o Primal-Dual, que parte
 de uma solucao viavel no dual e invia`vel no primal e caminha para uma
 solucao viavel inteira no primal satisfazendo custo(Primal) <= 3 custo(Dual),
 que, como sera` visto, implicara` numa 3 aproximacao.

 O metodo Primal-Dual nao gera a melhor aproximacao para o problema,
 porem tem a vantagem de ser bastante rapido.