Correlation clustering in data streams

DOI10.1007/s00453-021-00816-9OpenAlexW1836916015MaRDI QIDQ2037102

Anthony Wirth, Sudipto Guha, Graham Cormode, Andrew McGregor, Kook Jin Ahn

Publication date: 30 June 2021

Published in: Algorithmica (Search for Journal in Brave)

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

zbMATH Keywords

linear programmingdata streamscorrelation clusteringlinear sketches

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Graph theory (05Cxx)

Related Items (9)

An improved approximation algorithm for capacitated correlation clustering problem ⋮ Approximation algorithm for the capacitated correlation clustering problem with penalties ⋮ Approximation algorithms for two variants of correlation clustering problem ⋮ Distributed Symmetry Breaking on Power Graphs via Sparsification ⋮ Dynamic graph stream algorithms in \(o(n)\) space ⋮ Approximation algorithm for the balanced 2-correlation clustering problem on well-proportional graphs ⋮ Better streaming algorithms for the maximum coverage problem ⋮ A literature review on correlation clustering: cross-disciplinary taxonomy with bibliometric analysis ⋮ Approximation algorithms for the capacitated correlation clustering problem with penalties

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Improved approximation algorithms for MAX \(k\)-cut and MAX BISECTION
• Correlation clustering
• Graph-modeled data clustering: Exact algorithms for clique generation
• Lower bounds for one-way probabilistic communication complexity and their application to space complexity
• Cluster graph modification problems
• Linear programming in the semi-streaming model with application to the maximum matching problem
• Correlation clustering in general weighted graphs
• Clustering with qualitative information
• On graph problems in a semi-streaming model
• Near Optimal LP Rounding Algorithm for CorrelationClustering on Complete and Complete k-partite Graphs
• Single Pass Spectral Sparsification in Dynamic Streams
• A Local-Search 2-Approximation for 2-Correlation-Clustering
• Streaming Algorithms for k-Center Clustering with Outliers and with Anonymity
• Better streaming algorithms for clustering problems
• The Probabilistic Communication Complexity of Set Intersection
• Incremental Clustering and Dynamic Information Retrieval
• Approximate max-flow min-(multi)cut theorems and their applications
• Data stream clustering
• Aggregating inconsistent information

This page was built for publication: Correlation clustering in data streams