Hasso-Plattner-Institut
Prof. Dr. Tobias Friedrich
 

25.05.2021

Master project paper accepted at KDD

In the Winter 2020/21 Master Project the students Nicolas Klodt, Lars Seifert, and Arthur Zahn developed algorithms for the Chromatic Correlation Clustering problem in networks in which pairs of nodes can be joined by one of many similarities. The goal is to partition the nodes into clusters such that the similarities of the same type within a cluster are maximized, while minimizing the edges across clusters. This models for example social networks in which there are different kinds of relationships, like family, school mates, and colleagues from work. They presented a linear time 3-approximation algorithm for this NP-hard problem that beats the best-known polynomial time approximation guarantee so far. They also found a heuristic algorithm that empirically outperforms all previous algorithms. The results of the project have been accepted for publication at the 27th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), organized as a virtual conference on August 14-18 and hosted by the National University of Singapore.

Congratulations!

  • A Color-blind 3-Approxima... - Download
    Casel, Katrin; Friedrich, Tobias; Issac, Davis; Klodt, Nicolas; Seifert, Lars; Zahn, Arthur A Color-blind 3-Approximation for Chromatic Correlation Clustering and Improved HeuristicsKnowledge Discovery and Data Mining (KDD) 2021: 882–891