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.

  • 2
    $\begingroup$ Do you have n jobs and n people? In that case, you are looking for a minimum-cost matching in a bipartite graph where one side has degree 2, and the other side has average degree 2. If there are jobs that can only be done by one person, you know who you have to assign them to. If not, every person can do two jobs, and each job can be done by two people. $\endgroup$ – Peter Shor Apr 1 '14 at 1:17
  • $\begingroup$ @PeterShor thanks Peter. My case is second one, every person can do two jobs and each job can be done by two people. Do you think some optimization could be made for that case? $\endgroup$ – MoveFast Apr 1 '14 at 1:30
  • 7
    $\begingroup$ In that case, your graph is a collection of even-sized cycles. For each such cycle, there are two possible perfect matchings. By independence of the disconnected components, the cheaper of the two will be the one in the optimal matching. Thus, you can solve this problem in linear time by picking a vertex $v$, following it to a neighbor, and keep following to its next neighbor until you get back to $v$, closing the cycle. Then test the two possible matchings in this cycle, pick the cheapest one, and recurse on the rest of the graph. $\endgroup$ – Yonatan N Apr 1 '14 at 1:50
  • $\begingroup$ @YonatanN I am afraid I did not understand. Can you please explain with an example $\endgroup$ – MoveFast Apr 1 '14 at 2:02
  • $\begingroup$ minor pedantic note: your problem is a special case of the assignment problem. The Hungarian algorithm is a solution to this problem. $\endgroup$ – Suresh Venkat Apr 1 '14 at 2:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.