Seminário de Teoria da Computação Correlation Clustering Evandro C. Bracht Sexta-feira, 1 de outubro de 2004, Auditório do IC 13:00hs Resumo: No problema Correlation Clustering, assim como outros problemas de particionamento, o objetivo é criar uma partição onde objetos semelhantes estejam juntos na mesma parte enquanto que objetos não semelhantes pertençam a partes diferentes. Podemos interpretar a relação entre os objetos como um grafo $G=(V,E)$ onde as arestas $uv \in E$ são rotuladas com ``+'' se u é semelhante à v e ``-'' caso contrário. O problema Correlation Clustering pode considerar as seguintes funções objetivo: - Minimizar a discordância: Em uma partição, a discordância é dada pelo número de arestas positivas entre as partes somado com o número de arestas negativas internas à cada parte. - Maximizar a concordância: Em uma partição, a concordância é dada pelo número de arestas negativas entre as partes somado com o número de arestas positivas internas à cada parte. O que difere o problema Correlation Clustering da maioria dos outros problemas de particionamento é o fato de que o número $k$ de partes que devem ser criadas não é especificado e pode variar de 1 a n, onde n é o número de objetos. Neste seminário apresentaremos este problema bem como algoritmos de aproximação e um limitante usado nas provas do fator de aproximação.