Understanding the Cluster Linear Program for Correlation Clustering

Understanding the Cluster Linear Program for Correlation Clustering

June 24–28, 2024, Vancouver, BC, Canada | Nairen Cao, Vincent Cohen-Addad, Euiwoong Lee, Shi Li, Alantha Newman, Lukas Vogl
The paper introduces the *cluster LP* as a unified framework for the Correlation Clustering problem, which aims to partition vertices into clusters to minimize the number of misclassified edges. The cluster LP is designed to capture all previous relaxations and can be approximately solved in polynomial time, despite having exponentially many variables. This allows for a simpler and more unified approach to designing rounding algorithms without the need to handle correlated rounding errors separately. The authors propose a new rounding algorithm and analysis techniques that significantly improve the approximation ratio to 1.49, and further refine it to 1.437. They also prove a lower bound of 4/3 on the integrality gap of the cluster LP, which translates to an NP-hardness result for the problem. The paper provides detailed technical proofs and discusses the implications of the cluster LP for understanding the hardness and approximability of Correlation Clustering.The paper introduces the *cluster LP* as a unified framework for the Correlation Clustering problem, which aims to partition vertices into clusters to minimize the number of misclassified edges. The cluster LP is designed to capture all previous relaxations and can be approximately solved in polynomial time, despite having exponentially many variables. This allows for a simpler and more unified approach to designing rounding algorithms without the need to handle correlated rounding errors separately. The authors propose a new rounding algorithm and analysis techniques that significantly improve the approximation ratio to 1.49, and further refine it to 1.437. They also prove a lower bound of 4/3 on the integrality gap of the cluster LP, which translates to an NP-hardness result for the problem. The paper provides detailed technical proofs and discusses the implications of the cluster LP for understanding the hardness and approximability of Correlation Clustering.
Reach us at info@study.space
Understanding Understanding the Cluster Linear Program for Correlation Clustering