C1: Combinatorial Correlation Clustering

April 10, 2024

• Efficient MPC Algorithms for Correlation Clustering
  • Algorithm 1 (Basic 2-approximation local search algorithm)
  • An improved version of 15/8-approximation
    • The Process:
  • A Complex Version
• Reference

This post is based on [1].

Efficient MPC Algorithms for Correlation Clustering

Local Search is a powerful method for clustering problems. Again, this tool shows us its strength in correlation clustering.

Algorithm 1 (Basic 2-approximation local search algorithm)

Let \(S\) be the solution output by the algorithm and let OPT be the optimum solution.

  For each cluster C in OPT, 
             1) Consider S_C that is by inserting C 
             into S as a cluster and removing 
             elements from S. 
             2) Update S by inserting S_, reducing the cost.

The naive way of finding the \(S_C\) is using an exponential algorithm. Now, let us forget how to obtain \(S_C\) first and focus on the approximation ratio.

In the above picture, we use \(x_1, x_2\) with signal \(+\) to denote the increased cost by inserting \(C\) into \(S\) (for the nodes in \(C\)). We use \(y_1, y_2\) with signal \(-\) to denote the saved cost by inserting \(C\) into \(S\) (for nodes in \(C\)). Let \(comm\) to denote the common cost between the the optimal algorithm and an algorithm.

Due to local optimality, (it means that we cannot reduce the cost by inserting \(C\)), we have that

\[comm + x_1 + x_2 \geq comm + y_1 + y_2\]

We use \(cost(OPT)\) to denote the optimum cost and use \(cost(S)\) to denote the cost of an algorithm. Now, we get that

\[cost(OPT) = \sum_C comm+x_1/2 + x_2\] \[cost(S) = \sum_C comm+y_1 + y_2/2\]

Then, we have

\[\begin{aligned} cost(S) \leq \sum_C comm+y_1 + y_2 & \\ \leq \sum_C comm+x_1+x_2 & \\ \leq 2(\sum_C comm + x_1/2 + x_2) &\\ =2\cdot cost(OPT). \end{aligned}\]

An improved version of 15/8-approximation

Let \(Alg_i\) be a local optimum clustering with weights \(w_i\).

The Process:

1. Set \(Algo_1\) with weight function \(w_1\);

2. Double the weight of edges in \(E^+ \cap EXT(Alg_1)\) to get a new weight function \(w_2\) where \(EXT(?)\) is the edges across clusters.

3. Set \(Algo_2\) with weight function \(w_2\);

4. Output the best of \(Algo_1\) and \(Algo_2\).

A Complex Version

---

\(\color{red} \text{To be continued \ldots}\)

Reference

[1]. Combinatorial Correlation Clustering, Vincent Cohen-Addad, David Rasmussen Lolck, Marcin Pilipczuk, Mikkel Thorup, Shuyi Yan, and Hanwen Zhang. Proceedings of the Symposium on Theory of Computing (STOC) 2024.