Algoritmos de aproximação para o facility location problem

• Processo: 02/05715-3
• Modalidade de apoio: Bolsas no Brasil - Mestrado
• Data de Início da vigência: 01 de setembro de 2002
• Data de Término da vigência: 30 de junho de 2004
• Área de conhecimento: Ciências Exatas e da Terra - Ciência da Computação - Teoria da Computação
• Pesquisador responsável: Flávio Keidi Miyazawa
• Beneficiário: Luis Augusto Angelotti Meira
• Instituição Sede: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brasil
• Assunto(s): Algoritmos de aproximação Problemas de localização de facilidades
• Palavra(s)-Chave do Pesquisador: Algoritmos De Aproximacao

Resumo

Neste projeto estamos interessados em investigar o Problema de Localização de Facilidades FLP (Facility Location Problem) sob a abordagem de algoritmos de aproximação. Nosso interesse será focado em estratégias recentes desenvolvidas para este problema, principalmente aquelas que levam a bons fatores de aproximação e resultados práticos. Algoritmos de aproximação é uma das áreas que tem recebido grande atenção dos pesquisadores de otimização e teoria da computação nos últimos anos. Isto se deve às novas técnicas que têm surgido de caráter mais genérico, no desenvolvimento de algoritmos para problemas de otimização. Estas técnicas tem sido usadas recentemente para problemas de localização de facilidades, sendo que resultados muito próximos das soluções ótimas tem sido obtidos, para instâncias razoavelmente grandes. Nesta abordagem estamos interessados tanto em resultados teóricos como resultados práticos. Nossos estudos tanto na área de algoritmos de aproximação como nos problemas de localização de facilidades já estão em andamento, e já implementamos um dos algoritmos usando a técnica primaldual. (AU)