The partition problem

By Sunil Chopra, M. Rao. 1993

How researchers see this paper

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

In Algorithms & Complexity

Citations in the corpus

InstanceCut: From Edges to Instances with MultiCut (2016, methodology): “MultiCut Problem.”
DeepCut: Joint Subset Partition and Labeling for Multi Person Pose Estimation (2015, methodology): “The Minimum Cost Multicut Problem [9, 11], known in machine learning as correlation clustering [4], has been used in computer vision for image segmentation [1, 2, 19, 35] but has not been used before in the context of pose estimation.”
SSAP: Single-Shot Instance Segmentation With Affinity Pyramid (2019, methodology): “In this way, instance segmentation is transformed into a graph partition problem [11] and can be addressed by solving the following optimization problem [26]:”
Efficient Decomposition of Image and Mesh Graphs by Lifted Multicuts (2015, methodology): “We now apply both formulations of the graph decomposition problem, the Minimum Cost Multicut Problem (MP) [17] and the Minimum Cost Lifted Multicut Problem (LMP) defined in Sec.”
Asymmetric Cuts: Joint Image Labeling and Partitioning (2014, background): “For internal nodes, the cycle constraint (4a) [13,3] intuitively forbids dangling boundaries.”
Cut, Glue, & Cut: A Fast, Approximate Solver for Multicut Partitioning (2014, background): “In general, y ∈ MCG can be enforced by an exponential number of constraints [9], but in practice – for a given objective function – a small subset of those are sufficient.”
Motion Trajectory Segmentation via Minimum Cost Multicuts (2015, methodology): “The minimum cost multicut [10, 12] framework allows to formulate the trajectory segmentation as an unbalanced grouping problem - allowing for very small but reasonable segments to be retrieved.”
Handbook of Semidefinite Programming (2000, background): “Linear relaxations are investigated mostly for k = 2, and use additional combinatorial cutting planes, see [168, 151].”