Algoritmos para o problema de particionamento

Autor(es)

Thiago de Paulo Faleiros

• Tipo de documento: Dissertação de Mestrado
• Imprenta: Campinas, SP.
• Instituição: Universidade Estadual de Campinas (UNICAMP). Instituto de Computação
• Data de defesa: 2010-12-16

Membros da banca

Eduardo Candido Xavier; Luis Augusto Angelotti Meira; Guilherme Pimentel Telles

• Orientador: Eduardo Candido Xavier

Resumo

Investigamos Problemas de Particionamento de objetos que têm relações de similaridade entre si. Instâncias desses problemas podem ser representados por grafos, em que objetos são vértices e a similaridade entre dois objetos é representada por um valor associado à aresta que liga os objetos. O objetivo do problema é particionar os objetos de tal forma que objetos similares pertençam a um mesmo subconjunto de objetos. Nosso foco é o estudo de algoritmos para clusterização em grafos, onde deve-se determinar clusteres tal que arestas ligando vértices de clusteres diferentes tenham peso baixo e ao mesmo tempo as arestas entre vértices de um mesmo cluster tenha peso alto. Problemas de particionamento e clusterização possuem aplicações em diversas áreas, como mineração de dados, recuperação de informação, biologia computacional, entre outros. No caso geral estes problemas são NP-Difíceis. Nosso interesse é investigar algoritmos eficientes (com complexidade de tempo polinomial) e que gerem boas soluções, como Heurísticas, Metaheurísticas e Algoritmos de Aproximação. Dentre os algoritmos estudados, implementamos os mais promissores e fazemos uma comparação de seus resultados utilizando instâncias geradas computacionalmente. Por fim, propomos um algoritmo que utiliza a metaheurística GRASP para o problema considerado e mostramos que, para as instâncias de testes geradas, nosso algoritmo obtém melhores resultados (AU)

• Processo FAPESP: 08/06878-0 - Problemas de Classificação e Particionamento
• Beneficiário: Thiago de Paulo Faleiros
• Modalidade de apoio: Bolsas no Brasil - Mestrado