Problemas de Classificação e Particionamento

• Processo: 08/06878-0
• Modalidade de apoio: Bolsas no Brasil - Mestrado
• Data de Início da vigência: 01 de março de 2009
• Data de Término da vigência: 31 de agosto de 2010
• Área de conhecimento: Ciências Exatas e da Terra - Ciência da Computação - Teoria da Computação
• Pesquisador responsável: Eduardo Candido Xavier
• Beneficiário: Thiago de Paulo Faleiros
• Instituição Sede: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brasil
• Assunto(s): Algoritmos de aproximação Otimização combinatória Heurística
• Palavra(s)-Chave do Pesquisador: Algoritmos de Aproximação | Algoritmos probabilísticos | heuristicas | Problema de Classificação | Otimização Combinatória

Resumo

Neste projeto estamos interessados em investigar Problemas de Classificação e Particionamento de objetos que tem relações de similaridade entre si. Estes problemas podem ser representados por um grafo, onde os objetos são vértices e a similaridade entre dois objetos é representada por um valor associado à uma aresta (par de objetos). Os objetos devem ser particionados em grupos e também há custos associados a classificação dos objetos em cada um dos possíveis grupos. Nestes problemas, deve-se particionar os objetosde tal forma a minimizar o custo total das arestas entre objetos de partições diferentes bem como o custo de atribuição dos objetosa determinados grupos.Problemas de classificação possuem aplicações em diversas áreas como processamento de imagens, biologia computacional, detecção de spams dentre outros.Os problemas considerados são NP-difíceis no caso geral e nosso interesse é investigar algoritmos eficientes (com complexidade de tempo polinomial), como Algoritmos Probabilísticos, Algoritmos de Aproximação e Heurísticas. É nosso objetivo comparar e implementar os algoritmos mais promissores e comparar seus desempenhos com testes práticos.

Publicações acadêmicas

(Referências obtidas automaticamente das Instituições de Ensino e Pesquisa do Estado de São Paulo)

FALEIROS, Thiago de Paulo. Algoritmos para o problema de particionamento. 2010. Dissertação de Mestrado - Universidade Estadual de Campinas (UNICAMP). Instituto de Computação Campinas, SP.