Efficient Combinatorial Algorithm for Correlation Clustering

Paper Title:

Combinatorial Correlation Clustering

Published on:

8 April 2024

Primary Category:

Data Structures and Algorithms

Paper Authors:

Vincent Cohen-Addad,

David Rasmussen Lolck,

Marcin Pilipczuk,

Mikkel Thorup,

Shuyi Yan,

Hanwen Zhang

Bullets

Key Details

•

Achieves 1.847-approximation for Correlation Clustering, drastically better than previous 3-approx

•

Runs in sublinear time and space, using only constant rounds

•

First to break 2-approximation barrier efficiently

•

Resolves open question on achieving <3-approx in near linear time

•

New iterative local search method with adaptive weight updates

Explore the topics in this paper

approximation algorithms

combinatorial algorithms

correlation clustering

distributed algorithms

sublinear time algorithms

AI generated summary

Efficient Combinatorial Algorithm for Correlation Clustering

This paper presents a new combinatorial algorithm for the classic Correlation Clustering problem that achieves a 1.847-approximation factor, drastically improving over the previous best 3-approximation. The algorithm runs in sublinear time and space and uses only a constant number of rounds, making it highly efficient and practical.