I am working on a problem and it appears to be a special case of Hungarian algorithm.
- In Hungarian algorithm for assignment problem, there are n people and n jobs.
- Each person can do any of n jobs and incur a corresponding cost C. The goal is to minimize the cost by assigning n people to n jobs.
- My special case that for each person, he can be assigned only 2 specific jobs out of n jobs. Given this condition, is there any optimization possible for Hungarian algorithm that will reduce its complexity from O(n^3) to lower.
Thanks for your help.