Instance-Specific Approximation Ratios for Correlation Clustering and Max-Cut

For many NP-hard optimization problems, strong theoretical inapproximability results exist. However, in practice, heuristics regularly outperform these pessimistic worst-case results on real-world datasets. Assessing the quality of these algorithms' outputs is often difficult since we lack good lower bounds on the optimal solution. In this paper, we present efficient algorithms for computing lower bounds on the optimal solutions for correlation clustering, which is a popular problem in social-network analysis. Our lower bounds allow us to provide empirical certificates that bound the solution quality of practical algorithms by obtaining instance-specific approximation ratios. Our main technical contribution is an algorithm that approximates an LP relaxation of a related triangle covering problem in near-linear time on sparse graphs; the algorithm is based on the multiplicative weights update framework and runs on graphs with millions of edges in a few minutes. For the concrete problem of correlation clustering, our lower bounds certify that state-of-the-art heuristics achieve almost optimal approximation ratios of 0.94 for the agreement version and 1.97 for the disagreement version (averaged over 7 real-world datasets). We also show similar results for the fundamental max-cut problem.

For many optimization problems, algorithms that compute the best possible solution are impractical due to very high running times. Therefore, practitioners use efficient heuristics that return inexact solutions, and it is difficult to assess how good those solutions really are. This paper develops a way to bound the quality of solutions on individual datasets for the two network partitioning problems Correlation Clustering and Max-Cut. Our method efficiently finds a certificate showing how close a computed solution is to the optimal one. Experiments show that several practical methods produce answers that are just slightly worse than optimality on real-world datasets. Thus, the paper helps to explain why simple and fast graph algorithms work much better in practice than worst-case theory predicts.