<p>I am working on a problem and it appears to be a special case of Hungarian algorithm. </p>

<ul>
<li>In Hungarian algorithm for assignment problem, there are n people and n jobs. </li>
<li>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. </li>
<li>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.  </li>
</ul>

<p>Thanks for your help. </p>

CC BY-SA 3.0
2014-04-01T01:17:33.133Z
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.
Peter Shor 
CC BY-SA 3.0
2014-04-01T01:30:02.137Z
@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?
MoveFast
CC BY-SA 3.0
2014-04-01T01:50:43.207Z
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.
Yonatan N
CC BY-SA 3.0
2014-04-01T02:02:41.497Z
@YonatanN I am afraid I did not understand. Can you please explain with an example
MoveFast
CC BY-SA 3.0
2014-04-01T02:46:37.223Z
minor pedantic note: your problem is a special case of the assignment *problem*. The Hungarian algorithm is a *solution* to this problem.
Suresh Venkat
CC BY-SA 3.0
2014-04-02T18:46:40.693Z
@ManojGumber Refer to http://imgur.com/72SOcJf . You can do Step 2 by picking an uncolored vertex arbitrarily, picking a new color for it, and coloring each vertex reachable from it by DFS with the same color. Repeat until every vertex is colored. Each color represents an independent component, which has to be an even cycle (even, connected, degree-2 graph). Even cycles contain exactly 2 perfect matchings (blue and orange in step 3). Test the cost of both, and take the cheaper one. Repeat this process for each cycle (colored component), and return the union of all cheapest-matchings you found.
Yonatan N
<graph-theory><graph-algorithms><optimization>
Help with a special case for Hungarian algorithm
MoveFast
# Help with a special case for Hungarian algorithm

(Asked by: username_0 on 2014-04-01)

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.

**Tags:** graph-theory, graph-algorithms, optimization

> **Comments:**
> **username_1**: 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.  
> **username_0**: @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?  
> **username_2**: 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.  
> **username_0**: @YonatanN I am afraid I did not understand. Can you please explain with an example  
> **username_3**: minor pedantic note: your problem is a special case of the assignment *problem*. The Hungarian algorithm is a *solution* to this problem.  
> **username_2**: @ManojGumber Refer to http://imgur.com/72SOcJf . You can do Step 2 by picking an uncolored vertex arbitrarily, picking a new color for it, and coloring each vertex reachable from it by DFS with the same color. Repeat until every vertex is colored. Each color represents an independent component, which has to be an even cycle (even, connected, degree-2 graph). Even cycles contain exactly 2 perfect matchings (blue and orange in step 3). Test the cost of both, and take the cheaper one. Repeat this process for each cycle (colored component), and return the union of all cheapest-matchings you found.  

---

## 0 answers

