Full text
| |
| Author(s): |
Thiago de Paulo Faleiros
Total Authors: 1
|
| Document type: | Master's Dissertation |
| Press: | Campinas, SP. |
| Institution: | Universidade Estadual de Campinas (UNICAMP). Instituto de Computação |
| Defense date: | 2010-12-16 |
| Examining board members: |
Eduardo Candido Xavier;
Luis Augusto Angelotti Meira;
Guilherme Pimentel Telles
|
| Advisor: | Eduardo Candido Xavier |
| Abstract | |
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 results (AU) | |
| FAPESP's process: | 08/06878-0 - Classification and Partitioning Problems |
| Grantee: | Thiago de Paulo Faleiros |
| Support Opportunities: | Scholarships in Brazil - Master |