A note on the inapproximability of correlation clustering

DOI10.1016/j.ipl.2008.06.004zbMath1189.05158arXiv0704.2092OpenAlexW2004804027MaRDI QIDQ975483

Jinsong Tan

Publication date: 9 June 2010

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/0704.2092

zbMATH Keywords

graph algorithmsrandomized roundinginapproximabilitycorrelation clustering

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Nonnumerical algorithms (68W05) Graph theory (including graph drawing) in computer science (68R10) Signed and weighted graphs (05C22)

Cites Work

• Correlation clustering
• Toward efficient agnostic learning
• Clustering with qualitative information
• Probability Inequalities for Sums of Bounded Random Variables
• Algorithms - ESA 2003
• Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques
• Aggregating inconsistent information
• Unnamed Item
• Unnamed Item

This page was built for publication: A note on the inapproximability of correlation clustering