Approximate Dual Separation for the Cluster LP: a -approximation for Correlation ClusteringResearch Paper
Suppose every pair of vertices comes with a positive or negative judgment. A partition agrees with a positive judgment when the vertices lie in the same block and with a negative judgment when they lie in different blocks. MinDisagree asks for a partition with as few disagreements as possible. The number of blocks is unrestricted. This mission concerns…