Breaking 3-Factor Approximation for Correlation Clustering in Polylogarithmic Rounds
summary
The paper gives a parallel PRAM/MPC algorithm that breaks the 3× barrier, achieving 2.4+ε approximation in polylogarithmic rounds (poly(1/ε)·log^O(1) n) by replacing the standard LP triangle constraints with a cut/flow view, truncating paths to length two and reducing rounding to packing many disjoint positive–positive–negative triangles. The method is randomized, implements in MPC with superlinear memory and incurs m^{3/2} work (triangle-heavy), so it is low-depth but not yet practical for massive graphs.
AI-written summary · about
chapters (19)
- 0:00Introduction
- 0:31Problem overview
- 1:12What is correlation clustering
- 3:26Real-world applications
- 5:08Prior results
- 6:56Complete graph case
- 7:38Hardness and limits
- 8:48Parallel algorithms
- 9:53Main result
- 10:40Algorithm overview
- 13:12Why stuck at 3
- 17:40Sequential algorithms
- 21:42Parallelization challenges
- 23:29Relaxing constraints
- 24:12Triangle inequality vs cut
- 27:05Flow view and truncation
- 28:35Solving truncated flow
- 30:41Algorithm summary
- 31:05Q&A
related talks
20mTruly Stateless, Optimal Dynamic Partial Order Reduction
15mThread-modular Analysis of Release-Acquire Concurrency
23mProbabilistic Concurrent Reasoning in Outcome Logic: Independence, Conditioning, and(…)
16mEntanglement Detection with Near-Zero Cost
21mModel Checking C/C++ with Mixed-Size Accesses
39mThe best multicore-parallelization refactoring you've never heard of
20mFixed Parameter Tractable Linearizability Monitoring
15mRON: One-Way Circular Shortest Routing to Achieve Efficient and Bounded-waiting Spinlocks