Algorithms for partitioning problem

Orientador: Eduardo Candido XavierDissertação (mestrado) - Universidade Estadual de Campinas, Instituto de ComputaçãoResumo: 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 resultadosAbstract: In this work we investigate Partitioning Problems of objects for which a similarity relations is defined. Instance to these problems can be represented by graphs where vertices are objects, and the similarity between two objects is represented by a value associated with an edge that connects objects. The problem objective is to partition the objects such that similar objects belong to the same subset of objects. We study clustering algorithms for graphs, where clusters must be determined such that edges connecting vertices of different clusters have low weight while the edges between vertices of a same cluster have high weight. Partitioning and clustering problems have applications in many areas, such as data mining, information retrieval, computational biology, and others. Many versions of these problems are NP-Hard. Our interest is to study eficient algorithms (with polynomial time complexity) that generate good solutions, such as Heuristics, Approximation Algorithms and Metaheuristics. We implemented the most promising algorithms and compared their results using instances generated computationally. Finally, we propose a GRASP based algorithm for the partition and clustering problem and show that, for the generated test instances, our algorithm achieves better resultsMestradoMestre em Ciência da Computaçã