Abstract

Weighted correlation clustering is hard to solve and hard to approximate for general graphs. Its applications in network analysis and computer vision call for efficient algorithms. To this end, w make three contributions: We establish partial optimality conditions that can be checked efficientl and doing so recursively solves the problem for series-parallel graphs to optimality, in linear ti We exploit the packing dual of the problem to compute a heuristic, but non-trivial lower bound faster than that of a canonical linear program relaxation. We introduce a re-weighting with the dual solution by which efficient local search algo rithms converge to better feasible solutions. The effectiveness of our methods is demonstrated empirically on a number of benchmark instances.