suryajayaraman / hungarianalgorithm

C++implementation of Hungarian algorithm for Assignment problem

hungarianAlgorithm

• Repo contains C++ implementation of the famous Hungarian algorithm

• The Hungarian algorithm solves the optimal assignment problem in polynomial time ~O(n³)

• Eg : If the Cost of doing work for different workers can be tabulated as follows :

Worker / Task	Task 1	Task2	Task3	Task4
Worker A	5	9	3	6
Worker B	8	7	8	2
Worker C	6	10	12	7
Worker D	3	10	8	6

• The optimal assignment for the above is

  • Worker A -> Task 3
  • Worker B -> Task 4
  • Worker C -> Task 2
  • Worker D -> Task 1

• Total Optimal cost = 3 + 2 + 10 +3 = 18

• The implementation is forked from the wonderful repo but has been improved upon by

  • Using Eigen library for array operations
  • Added docstring and flowchart for better understanding of implementation

• Theoretically, it solves the primal-dual optimization problem. Reference : NPTEL operations research course )

Algorithm workflow

Requirements

The code was developed on Ubuntu 20.04 LTS OS with

• g++ 9.4.0
• cmake 3.16.3
• Eigen 3.3

How to run the project

$ git clone https://github.com/suryajayaraman/hungarianAlgorithm.git
$ cd hungarianAlgorithm
$ mkdir -p build && cd build
$ cmake ..
$ make
$ ./HUNGARIAN_ALGORITHM

Applications of Hungarian algorithm

• It is used for solving Data association problem in Object Tracking Applications as explained in this blog post

• In the following image, we need to associate the detections from Lidar to detections in camera. Essentially, hungarian algorithm can be used to associate data from different sensors, so as to fuse them to get better estimations

Image reference

• It's also one of the foundations for Algorithms like SORT (Simple Online and Realtime tracking)

References

• thinkautonomous blog post
• wiki page
• Markus Buehren inspired c++ implementation
• Python implementation
• C implementation with explanation
• c++ implementation
• Comparison of assignment problem implementation
• cpp best practices