Reviews: Correlation clustering with local objectives

This paper studies a number of versions of the correlation clustering problem. One is given a (not-necessarily complete) graph G(V,E,E-) with positive and negative edges, and seeks a partition of the vertices that minimizes the \ell_q norm of the "disagreement vector" --- that is, of the vector having in position v (for v \in V) the number of positive neighbors of v that are not in v's cluster, plus the number of negative neighbors of v that are in v's cluster. The usual correlation clustering problem minimizes the \ell_1 norm of the vector (that is, the total number of "mistakes" made by the partition). The \ell_q generalization of the correlation clustering problem was introduced by Puleo et al (2016). Currently, the best algorithms known (i) for complete graphs, general q, is a 7-approximation, (ii) for general graphs, q \infty, is a O(\sqrt{n}) approximation.