Simple Iterative Heuristics for Correlation Clustering

Summary, in English

A straightforward natural iterative heuristic for correlation clustering in the general setting is to start from singleton clusters and whenever merging two clusters improves the current quality score merge them into a single cluster. We analyze the approximation and complexity aspects of this heuristic and its randomized variant where two clusters to merge are chosen uniformly at random among cluster pairs amenable to merge.

• Författare: Andrzej Lingas; Mia Persson
• Avdelning/ar: Institutionen för datavetenskap; Parallella System
• Publiceringsår: 2014
• Språk: Engelska
• Sidor: 264-271
• Publikation/Tidskrift/Serie: Large-Scale Scientific Computing, LSSC 2013
• Volym: 8353
• Länkar: http://dx.doi.org/10.1007/978-3-662-43880-0_29
• Dokumenttyp: Konferensbidrag
• Förlag: Springer
• Ämne: Computer Science
• Conference name: 9th International Conference on Large-Scale Scientific Computations (LSSC)
• Conference date: 2013-06-03 - 2013-06-07
• Status: Published
• ISBN/ISSN/Övrigt: ISSN: 1611-3349; ISSN: 0302-9743