The Hungarian method for the assignment problem

By H. Kuhn. 1955

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

End-to-End Object Detection with Transformers (2020, neutral): “The usual solution is to design a loss based on the Hungarian al-gorithm [20], to ﬁnd a bipartite matching between ground-truth and prediction.”
Object-Centric Learning with Slot Attention (2020, methodology): “As the order of both predictions and labels is arbitrary, we match them using the Hungarian algorithm [35].”
Invariant Information Clustering for Unsupervised Image Classification and Segmentation (2018, methodology): “For IIC we follow the standard protocol of finding the best one-to-one permutation mapping between learned and ground-truth clusters (from the main output head; auxiliary overclustering head is ignored) using linear assignment [35].”
Multiset-Equivariant Set Prediction with Approximate Implicit Differentiation (2021, methodology): “Throughout the experiments, we make use of the Hungarian loss (Kuhn, 1955): It ﬁnds the optimal 1-to-1 mapping from each element in the prediction (1) n ] to each element in the ground-truth (2) n ] (cid:62) , minimizing the total pairwise losses.”
MERLOT: Multimodal Neural Script Knowledge Models (2021, methodology): “3); for CLIP and UNITER we compute a maximum-weight matching [52] over the pairwise image-text similarity scores.”
BASE Layers: Simplifying Training of Large, Sparse Models (2021, methodology): “We use the auction algorithm described in Bertsekas (1992), which is more easily parallelizable on GPUs than the Hungarian Algorithm (Kuhn, 1955).”
Unsupervised Learning by Predicting Noise (2017, background): “(5) to this set, the linear assignment problem in P can be solved exactly with the Hungarian algorithm (Kuhn, 1955), but at the pro-hibitive cost of O ( n 3 ) .”
It’s All in the Name: Mitigating Gender Bias with Name-Based Counterfactual Data Substitution (2019, methodology): “5 The problem of ﬁnding name-pairs thus decomposes into a Euclidean-distance bipartite matching problem, which can be solved using the Hungarian method (Kuhn, 1955).”
MaX-DeepLab: End-to-End Panoptic Segmentation with Mask Transformers (2020, methodology): “The optimal assignment is computed efficiently with the Hungarian algorithm [51], following prior work [10, 82].”
Federated Learning with Matched Averaging (2020, methodology): “Solving matched averaging Objective function in equation 2 can be optimized using an iterative procedure: applying the Hungarian matching algorithm (Kuhn, 1955) to find permutation {π ′ li }l,i corresponding to dataset j′, holding other permutations {π li}l,i,j 6=j′ fixed and iterating over the data”
Bayesian Nonparametric Federated Learning of Neural Networks (2019, methodology): “, 2018), where the authors use the BBP for modeling topics learned from multiple collections of document, and provide an inference scheme based on the Hungarian algorithm (Kuhn, 1955).”
SMArT: Training Shallow Memory-aware Transformers for Robotic Explainability (2019, methodology): “We compute the optimal assignment between them and the set of ground-truth classes c∗, using distances between word vectors and the Hungarian algorithm [38].”
Auto-Keras: An Efficient Neural Architecture Search System (2018, methodology): “The weighted bipartite graph matching problem is solved by the Hungarian algorithm (Kuhn-Munkres algorithm) [19].”
Stacked Capsule Autoencoders (2019, methodology): “This is done with one of the following methods: LIN-MATCH: after finding 10 clusters9 with KMEANS we use bipartite graph matching (Kuhn, 1955) to find the permutation of cluster indices that minimizes the classification error—this is standard practice in unsupervised classification, see e.”
Towards exact molecular dynamics simulations with machine-learned force fields (2018, methodology): “Then −M is provided as the cost matrix for the Hungarian algorithm [56], maximizing the overall overlap which finally returns the approximate assignment τ̃ that minimizes Eq.”
Machine learning unifies the modeling of materials and molecules (2017, positive): “For example, setting P to be the permutation matrix that maximizes the value of K corresponds to the “best match” assignment between constituent atoms in the two structures that are compared, which can be computed in polynomial time by formulating the task as an optimal assignment problem (42).”
Novel Class Discovery without Forgetting (2022, methodology): “where perm(Yunlab) is a set of permutations of the unlabeled classes optimally computed via the Hungarian algorithm [30] and Nu refers to the number of instances in Dunlab.”