0

I have a problem where I have to pair workers to perform task. This means that each pair p-q can only perform a task t. I have to optimally find for each task t, which pair can best perform the task optimally for assignment.

How can I convert this problem to a matrix that I can solve using the Hungarian algorithm because obviously this cannot be a nxn matrix that is easily solved by the algorithm. Or is there an algorithm that I can use for such a case?

leutsoa moteka
  • 1
  • 1
  • Is there some kind of weighting here that you haven't mentioned? The Hungarian algorithm is for weighted bipartite matching. If I understand your description, the problem you have is neither bipartite nor weighted, so I wonder why you think the Hungarian algorithm would be applicable. When I say it isn't bipartite, I mean I don't see why worker $p$ couldn't be paired with $q$ to do task $t$ or paired with $r$ to do task $s$. – saulspatz Aug 19 '18 at 21:39
  • Hi, this is for a weighted bipartite graph, where the weight w of each edge is the cost that each group of two workers p-q can do for task t.

    So I need to find an optimal assingment for each group of users to each task.

     – leutsoa moteka Aug 20 '18 at 09:45
  • So no worker belongs to more than one group? If this is so, I don't see the problem. The Hungarian does not require that the number of tasks and the number of (pairs of) workers be the same. – saulspatz Aug 20 '18 at 16:39
  • If I have (p-q) pairs on the left side say, Set A, and then I only have t tasks on the right side say Set B.

    How do I apply the Hungarian Algorithm such that I find optimal matching of pairs to tasks. Remember:

    ................p1 can either be matched with (q1,q2 . . .) for task t1 also..................... p2 can either be matched with (q1,q2 . . .) for task t1 ...............p3 can either be matched with (q1,q2 . . .) for task t1

    BUUUT If p1__q2 matching is optimal for t1, then p1__q1 is no longer relevant.

     – leutsoa moteka Aug 21 '18 at 08:53
  • This is not really a bipartite graph. It's a weighted $3-$uniform hypergraph. The Hungarian algorithm doesn't apply directly. What leads you to believe that it can be made to work? – saulspatz Aug 21 '18 at 12:36
  • Wait a bit. Is there something different about the p's and q's? Is it something like each task requires a designer and a developer and no one is both a designer and a developer? – saulspatz Aug 21 '18 at 12:42
  • Alright,I'm currently looking at hypergraphs to see if they can work here. Yes, absolutely. Its like each task t needs both designer d from set A and developer p from Set B but these are all from a set of users. But I need to choose the designer-developer pair wise and optimally for each task on the right. I also tried looking into Hopcroft-Karp Algorithm, i am not sure if it can perform the optimum assingment. – leutsoa moteka Aug 21 '18 at 21:25
  • Apparently, even the unweighted problem is NP-hard. I've done some Googling, and found out that the (unweighted) problem is called three-dimensional matching. – saulspatz Aug 21 '18 at 23:05
  • Alright thank you. Are there existing algorithms that solve these types of bipartite graphs you know? I will look to see if there are some that exist. – leutsoa moteka Aug 22 '18 at 08:55
  • No, I don't know any way to solve problems like this. Sorry. – saulspatz Aug 22 '18 at 08:57
  • Thanks for the insight though. – leutsoa moteka Aug 22 '18 at 09:04
  • Thanks you for introducing me to this problem. I've always liked matching. – saulspatz Aug 22 '18 at 09:07

0 Answers0