Correlation clustering in general weighted graphs

By Erik D. Demaine, Dotan Emanuel, Amos Fiat, Nicole Immorlica. Theoretical Computer Science, 2006

359 citations recorded by the source corpus.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Multiple People Tracking by Lifted Multicut and Person Re-identification (2017, background): “The minimum cost lifted multicut problem defined by (4) is APX-hard [8].”
Efficient Decomposition of Image and Mesh Graphs by Lifted Multicuts (2015, background): “One disadvantage is the NP-hardness of the MP [11, 18].”
Large-Scale Deduplication with Constraints Using Dedupalog (2009, background): “In fact, for some natural variants of the clustering problem it is believed that no algorithm can even give a bounded approximation guarantee [15].”
DeeperCut: A Deeper, Stronger, and Faster Multi-person Pose Estimation Model (2016, background): “DeeperCut is also able to correctly assemble body parts even for rare body articulations as in the image 25.”
Subgraph decomposition for multi-target tracking (2015, methodology): “The Minimum Cost Subgraph Multicut Problem is NP-hard [4] and APXhard [7].”
Motion Trajectory Segmentation via Minimum Cost Multicuts (2015, background): “Although problem defined in equation (1) is NP-hard [5] and even APX-hard [11], instances have been solved within tight bounds or even to optimality in for example [2] using the constrained integer linear programming (ILP) problem formulation from equation 1 and branch-and-cut.”