Problema das k-medianas.

• Processo: 05/54396-6
• Modalidade de apoio: Bolsas no Brasil - Iniciação Científica
• Data de Início da vigência: 01 de agosto de 2005
• Data de Término da vigência: 31 de julho de 2006
• Á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: Gabriel Pedro de Castro
• Instituição Sede: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brasil
• Assunto(s): Algoritmos de aproximação
• Palavra(s)-Chave do Pesquisador: Algoritmos De Aproximacao | Problemas Da K-Mediana

Resumo

Neste projeto estamos interessados em estudar o Problema das k-medianas (k-medians) sob a abordagem de algoritmos de aproximação. O problema das k-medianas é um dos principais problemas em clustering com diversas aplicações em classificação de documentos, objetos, páginas da internet, etc. 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 têm sido usadas recentemente para o problema das k-medianas, sendo que resultados muito próximos das soluções ótimas tem sido obtido, para instâncias razoavelmente grandes. Neste projeto pretendemos aprender diversas técnicas em algoritmos de aproximação aplicadas ao problema da k-mediana, Além disso, pretendemos implementar alguns destes algoritmos que indicarem um bom comportamento prático. (AU)