Multi-multiway cuts with edge labels

We consider a natural generalization of both the multi-multiway cut and correlation clustering problems: the problem of multi-multiway cut with edge labels. The input to the problem is an undirected graph G=(V, E) with real nonnegative edge weights and k sets S₁, S₂, ..., S_k of vertices, where each edge (u, v) is labeled either + or - depending on whether u and v have been deemed to be similar or dissimilar. The goal is to partition the vertices of G into clusters to minimize the total weight of cut + edges and uncut - edges, with the restriction that every pair of vertices u, visinS_i for some i must be in different clusters. We present an O(nlogn)-approximation algorithm for this problem, where n is the number of vertices of G.