assignment problem graph theory

Reset password New user? Sign up

Existing user? Log in

Hungarian Maximum Matching Algorithm

Already have an account? Log in here.

The Hungarian matching algorithm , also called the Kuhn-Munkres algorithm, is a \(O\big(|V|^3\big)\) algorithm that can be used to find maximum-weight matchings in bipartite graphs , which is sometimes called the assignment problem . A bipartite graph can easily be represented by an adjacency matrix , where the weights of edges are the entries. Thinking about the graph in terms of an adjacency matrix is useful for the Hungarian algorithm.

A matching corresponds to a choice of 1s in the adjacency matrix, with at most one 1 in each row and in each column.

The Hungarian algorithm solves the following problem:

In a complete bipartite graph \(G\), find the maximum-weight matching. (Recall that a maximum-weight matching is also a perfect matching.)

This can also be adapted to find the minimum-weight matching.

Say you are having a party and you want a musician to perform, a chef to prepare food, and a cleaning service to help clean up after the party. There are three companies that provide each of these three services, but one company can only provide one service at a time (i.e. Company B cannot provide both the cleaners and the chef). You are deciding which company you should purchase each service from in order to minimize the cost of the party. You realize that is an example of the assignment problem, and set out to make a graph out of the following information: \(\quad\) Company\(\quad\) \(\quad\) Cost for Musician\(\quad\) \(\quad\) Cost for Chef\(\quad\) \(\quad\) Cost for Cleaners\(\quad\) \(\quad\) Company A\(\quad\) \(\quad\) $108\(\quad\) \(\quad\) $125\(\quad\) \(\quad\) $150\(\quad\) \(\quad\) Company B\(\quad\) \(\quad\) $150\(\quad\) \(\quad\) $135\(\quad\) \(\quad\) $175\(\quad\) \(\quad\) Company C\(\quad\) \(\quad\) $122\(\quad\) \(\quad\) $148\(\quad\) \(\quad\) $250\(\quad\) Can you model this table as a graph? What are the nodes? What are the edges? Show Answer The nodes are the companies and the services. The edges are weighted by the price.

What are some ways to solve the problem above? Since the table above can be thought of as a \(3 \times 3\) matrix, one could certainly solve this problem using brute force, checking every combination and seeing what yields the lowest price. However, there are \(n!\) combinations to check, and for large \(n\), this method becomes very inefficient very quickly.

The Hungarian Algorithm Using an Adjacency Matrix

The hungarian algorithm using a graph.

With the cost matrix from the example above in mind, the Hungarian algorithm operates on this key idea: if a number is added to or subtracted from all of the entries of any one row or column of a cost matrix, then an optimal assignment for the resulting cost matrix is also an optimal assignment for the original cost matrix.

The Hungarian Method [1] Subtract the smallest entry in each row from all the other entries in the row. This will make the smallest entry in the row now equal to 0. Subtract the smallest entry in each column from all the other entries in the column. This will make the smallest entry in the column now equal to 0. Draw lines through the row and columns that have the 0 entries such that the fewest lines possible are drawn. If there are \(n\) lines drawn, an optimal assignment of zeros is possible and the algorithm is finished. If the number of lines is less than \(n\), then the optimal number of zeroes is not yet reached. Go to the next step. Find the smallest entry not covered by any line. Subtract this entry from each row that isn’t crossed out, and then add it to each column that is crossed out. Then, go back to Step 3.

Solve for the optimal solution for the example in the introduction using the Hungarian algorithm described above. Here is the initial adjacency matrix: Subtract the smallest value in each row from the other values in the row: Now, subtract the smallest value in each column from all other values in the column: Draw lines through the row and columns that have the 0 entries such that the fewest possible lines are drawn: There are 2 lines drawn, and 2 is less than 3, so there is not yet the optimal number of zeroes. Find the smallest entry not covered by any line. Subtract this entry from each row that isn’t crossed out, and then add it to each column that is crossed out. Then, go back to Step 3. 2 is the smallest entry. First, subtract from the uncovered rows: Now add to the covered columns: Now go back to step 3, drawing lines through the rows and columns that have 0 entries: There are 3 lines (which is \(n\)), so we are done. The assignment will be where the 0's are in the matrix such that only one 0 per row and column is part of the assignment. Replace the original values: The Hungarian algorithm tells us that it is cheapest to go with the musician from company C, the chef from company B, and the cleaners from company A. We can verify this by brute force. 108 + 135 + 250 = 493 108 + 148 + 175 = 431 150 + 125 + 250 = 525 150 + 148 + 150 = 448 122 + 125 + 175 = 422 122 + 135 + 150 = 407. We can see that 407 is the lowest price and matches the assignment the Hungarian algorithm determined. \(_\square\)

The Hungarian algorithm can also be executed by manipulating the weights of the bipartite graph in order to find a stable, maximum (or minimum) weight matching. This can be done by finding a feasible labeling of a graph that is perfectly matched, where a perfect matching is denoted as every vertex having exactly one edge of the matching.

How do we know that this creates a maximum-weight matching?

A feasible labeling on a perfect match returns a maximum-weighted matching. Suppose each edge \(e\) in the graph \(G\) connects two vertices, and every vertex \(v\) is covered exactly once. With this, we have the following inequality: \[w(M’) = \sum_{e\ \epsilon\ E} w(e) \leq \sum_{e\ \epsilon\ E } \big(l(e_x) + l(e_y)\big) = \sum_{v\ \epsilon\ V} l(v),\] where \(M’\) is any perfect matching in \(G\) created by a random assignment of vertices, and \(l(x)\) is a numeric label to node \(x\). This means that \(\sum_{v\ \epsilon\ V}\ l(v)\) is an upper bound on the cost of any perfect matching. Now let \(M\) be a perfect match in \(G\), then \[w(M) = \sum_{e\ \epsilon\ E} w(e) = \sum_{v\ \epsilon\ V}\ l(v).\] So \(w(M’) \leq w(M)\) and \(M\) is optimal. \(_\square\)

Start the algorithm by assigning any weight to each individual node in order to form a feasible labeling of the graph \(G\). This labeling will be improved upon by finding augmenting paths for the assignment until the optimal one is found.

A feasible labeling is a labeling such that

\(l(x) + l(y) \geq w(x,y)\ \forall x \in X, y \in Y\), where \(X\) is the set of nodes on one side of the bipartite graph, \(Y\) is the other set of nodes, \(l(x)\) is the label of \(x\), etc., and \(w(x,y)\) is the weight of the edge between \(x\) and \(y\).

A simple feasible labeling is just to label a node with the number of the largest weight from an edge going into the node. This is certain to be a feasible labeling because if \(A\) is a node connected to \(B\), the label of \(A\) plus the label of \(B\) is greater than or equal to the weight \(w(x,y)\) for all \(y\) and \(x\).

A feasible labeling of nodes, where labels are in red [2] .

Imagine there are four soccer players and each can play a few positions in the field. The team manager has quantified their skill level playing each position to make assignments easier.

How can players be assigned to positions in order to maximize the amount of skill points they provide?

The algorithm starts by labeling all nodes on one side of the graph with the maximum weight. This can be done by finding the maximum-weighted edge and labeling the adjacent node with it. Additionally, match the graph with those edges. If a node has two maximum edges, don’t connect them.

Although Eva is the best suited to play defense, she can't play defense and mid at the same time!

If the matching is perfect, the algorithm is done as there is a perfect matching of maximum weights. Otherwise, there will be two nodes that are not connected to any other node, like Tom and Defense. If this is the case, begin iterating.

Improve the labeling by finding the non-zero label vertex without a match, and try to find the best assignment for it. Formally, the Hungarian matching algorithm can be executed as defined below:

The Hungarian Algorithm for Graphs [3] Given: the labeling \(l\), an equality graph \(G_l = (V, E_l)\), an initial matching \(M\) in \(G_l\), and an unmatched vertex \(u \in V\) and \(u \notin M\) Augmenting the matching A path is augmenting for \(M\) in \(G_l\) if it alternates between edges in the matching and edges not in the matching, and the first and last vertices are free vertices , or unmatched, in \(M\). We will keep track of a candidate augmenting path starting at the vertex \(u\). If the algorithm finds an unmatched vertex \(v\), add on to the existing augmenting path \(p\) by adding the \(u\) to \(v\) segment. Flip the matching by replacing the edges in \(M\) with the edges in the augmenting path that are not in \(M\) \((\)in other words, the edges in \(E_l - M).\) Improving the labeling \(S \subseteq X\) and \(T \subseteq Y,\) where \(S\) and \(T\) represent the candidate augmenting alternating path between the matching and the edges not in the matching. Let \(N_l(S)\) be the neighbors to each node that is in \(S\) along edges in \(E_l\) such that \(N_l(S) = \{v|\forall u \in S: (u,v) \in E_l\}\). If \(N_l(S) = T\), then we cannot increase the size of the alternating path (and therefore can't further augment), so we need to improve the labeling. Let \(\delta_l\) be the minimum of \(l(u) + l(v) - w(u,v)\) over all of the \(u \in S\) and \(v \notin T\). Improve the labeling \(l\) to \(l'\): If \(r \in S,\) then \(l'(r) = l(r) - \delta_l,\) If \(r \in T,\) then \(l'(r) = l(r) + \delta_l.\) If \(r \notin S\) and \(r \notin T,\) then \(l'(r) = l(r).\) \(l'\) is a valid labeling and \(E_l \subset E_{l'}.\) Putting it all together: The Hungarian Algorithm Start with some matching \(M\), a valid labeling \(l\), where \(l\) is defined as the labelling \(\forall x \in X, y \in Y| l(y) = 0, l(x) = \text{ max}_{y \in Y}(w\big(x, y)\big)\). Do these steps until a perfect matching is found \((\)when \(M\) is perfect\():\) (a) Look for an augmenting path in \(M.\) (b) If an augmenting path does not exist, improve the labeling and then go back to step (a).

Each step will increase the size of the matching \(M\) or it will increase the size of the set of labeled edges, \(E_l\). This means that the process will eventually terminate since there are only so many edges in the graph \(G\). [4]

When the process terminates, \(M\) will be a perfect matching. By the Kuhn-Munkres theorem , this means that the matching is a maximum-weight matching.

The algorithm defined above can be implemented in the soccer scenario. First, the conflicting node is identified, implying that there is an alternating tree that must be reconfigured.

There is an alternating path between defense, Eva, mid, and Tom.

To find the best appropriate node, find the minimum \(\delta_l\), as defined in step 4 above, where \(l_u\) is the label for player \(u,\) \(l_v\) is the label for position \(v,\) and \(w_{u, v}\) is the weight on that edge.

The \(\delta_l\) of each unmatched node is computed, where the minimum is found to be a value of 2, between Tom playing mid \((8 + 0 – 6 = 2).\)

The labels are then augmented and the new edges are graphed in the example. Notice that defense and mid went down by 2 points, whereas Eva’s skillset got back two points. However, this is expected as Eva can't play in both positions at once.

Augmenting path leads to relabeling of nodes, which gives rise to the maximum-weighted path.

These new edges complete the perfect matching of the graph, which implies that a maximum-weighted graph has been found and the algorithm can terminate.

The complexity of the algorithm will be analyzed using the graph-based technique as a reference, yet the result is the same as for the matrix-based one.

Algorithm analysis [3] At each \(a\) or \(b\) step, the algorithm adds one edge to the matching and this happens \(O\big(|V|\big)\) times. It takes \(O\big(|V|\big)\) time to find the right vertex for the augmenting (if there is one at all), and it is \(O\big(|V|\big)\) time to flip the matching. Improving the labeling takes \(O\big(|V|\big)\) time to find \(\delta_l\) and to update the labelling accordingly. We might have to improve the labeling up to \(O\big(|V|\big)\) times if there is no augmenting path. This makes for a total of \(O\big(|V|^2\big)\) time. In all, there are \(O\big(|V|\big)\) iterations each taking \(O\big(|V|\big)\) work, leading to a total running time of \(O\big(|V|^3\big)\).

• Matching Algorithms
• Bruff, D. The Assignment Problem and the Hungarian Method . Retrieved June 26, 2016, from http://www.math.harvard.edu/archive/20_spring_05/handouts/assignment_overheads.pdf
• Golin, M. Bipartite Matching & the Hungarian Method . Retrieved Retrieved June 26th, 2016, from http://www.cse.ust.hk/~golin/COMP572/Notes/Matching.pdf
• Grinman, A. The Hungarian Algorithm for Weighted Bipartite Graphs . Retrieved June 26, 2016, from http://math.mit.edu/~rpeng/18434/hungarianAlgorithm.pdf
• Golin, M. Bipartite Matching & the Hungarian Method . Retrieved June 26, 2016, from http://www.cse.ust.hk/~golin/COMP572/Notes/Matching.pdf

Problem Loading...

Note Loading...

Set Loading...

Stack Exchange Network

Stack Exchange network consists of 183 Q&A communities including Stack Overflow , the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Q&A for work

Connect and share knowledge within a single location that is structured and easy to search.

Relationship Between "Assignment Problems" and "Graphs"

I was reading the following Wikipedia Article on "Assignment Problems" that talks about the relationship between Assignment Problems and Graph Theory ( https://en.wikipedia.org/wiki/Assignment_problem ) :

The assignment problem is a fundamental combinatorial optimization problem. In its most general form, the problem is as follows:

The problem instance has a number of agents and a number of tasks. Any agent can be assigned to perform any task, incurring some cost that may vary depending on the agent-task assignment. It is required to perform as many tasks as possible by assigning at most one agent to each task and at most one task to each agent, in such a way that the total cost of the assignment is minimized.

Alternatively, describing the problem using graph theory: The assignment problem consists of finding, in a weighted bipartite graph, a matching of a given size, in which the sum of weights of the edges is minimum.

I am familiar with both of these concepts individually, but I do not understand why these concepts are related:

1) Assignment Problems

Assignment Problems - as the name implies - are usually about determining an "optimal assignment of tasks to agents". For example, suppose there are 4 Workers (Worker A, Worker B, Worker C, Worker D) and 4 Jobs (Job A, Job B, Job C, Job D). Each worker has a "certain cost" associated with performing each of these jobs (e.g. Worker A performs Job B better than Worker D, but Worker D performs Job D better than Worker A). The Assignment Problem involves "assigning" only one job to each worker such that the total cost is minimized:

2) Weighted Bipartite Graphs

A Bipartite Graph is a Graph in which all "Nodes" within the Graph (i.e. circles) either belong to one of two sets (e.g. red and blue). A Weighted Bipartite Graph is a Bipartite Graph in which each "Edge" has a certain cost associated with it:

My Question: The formal definition of a general Assignment Problem is seen below:

Thus, can someone please explain why " the assignment problem consists of finding, in a weighted bipartite graph, a matching of a given size, in which the sum of weights of the edges is minimum" ?

• optimization
• combinatorial-optimization

• 1 $\begingroup$ Let yellow be the agents A, B, C, D. Let blue be the tasks job1, job 2, job 3, job 4. Let the cost of each edge be the corresponding entry of the assignment cost matrix. Now minimize the cost of the matching. That seems like a pretty good correspondence to me. $\endgroup$ –  Mark L. Stone Commented Feb 10, 2022 at 17:57
• $\begingroup$ @ Mark L Stone: Thank you for your reply! I can see that the Assignment Problem does correspond to a Weighted Bipartite Graph , and that we want to find the sum of weights of the edges in minimum .... but why do we want to find a "matching"? $\endgroup$ –  stats_noob Commented Feb 10, 2022 at 18:01
• $\begingroup$ I think this is just a formality that corresponds to the constraint - a "matching" is a graph where each edge is without common vertices. I guess this is to make sure that a worker can not be assigned more than one job? thank you so much! $\endgroup$ –  stats_noob Commented Feb 10, 2022 at 18:05
• 1 $\begingroup$ Each node in the yellow should be matched to exactly one node in the blue. Just as each agent should be assigned (matched) to exactly one task. No agent can be assigned more than one task, and no task can be assigned to more than one agent. $\endgroup$ –  Mark L. Stone Commented Feb 10, 2022 at 18:23

Know someone who can answer? Share a link to this question via email , Twitter , or Facebook .

Your answer, sign up or log in, post as a guest.

Required, but never shown

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy .

Browse other questions tagged optimization combinatorial-optimization or ask your own question .

• Featured on Meta
• Bringing clarity to status tag usage on meta sites
• We've made changes to our Terms of Service & Privacy Policy - July 2024
• Announcing a change to the data-dump process

Hot Network Questions

• Whether and when this sum will converge?
• Did US troops insist on segregation in British pubs?
• Unsupervised classifier, no data in training input
• Are automorphisms of matrix algebras necessarily determinant preservers?
• Why are the titles of certain types of works italicized?
• Why does my Bluetooth speaker keep on connecting and disconnecting?
• Has the government of Afghanistan clarified what they mean/intend by the ban on 'images of living beings'?
• Group automorphism fixing finite-index subgroup
• Chord definition misunderstanding
• An integral using Mathematica or otherwise
• How to justify a ban on exclusivist religions?
• How can I address my colleague communicating with us via chatGPT?
• Can the speed of light inhibit the synchronisation of a power grid?
• TeXbook Exercise 21.10 Answer
• What is the lesson of the Book of Iyov for the "average" person
• Sticker on caption phone says that using the captions can be illegal. Why?
• Will this be the first time, that there are more People an ISS than seats in docked Spacecraft?
• Why are volumes of revolution typically taught in Calculus 2 and not Calculus 3?
• Meaning of capacitor "× 2" symbol on data sheet schematic
• Are there any original heat shield tiles on any of the retired space shuttles that flew to space?
• how replicate this effect with geometry nodes
• Aftermarket stereo wiring help for 2012 chevy colorado WT
• Is it possible to approximately compile Toffoli using H and CSWAP?
• How to calculate APR and amount owed

Are you an EPFL student looking for a semester project?

Work with us on data science and visualisation projects , and deploy your project as an app on top of GraphSearch.

Learn more about Graph Apps .

Assignment problem

• https://en.wikipedia.org/wiki/Assignment_problem

Copyright © 2024 EPFL, all rights reserved

Efficient Allocations in Constant Time: Towards Scalable Solutions in the Era of Large Scale Intelligent Systems

Boi Faltings , Panayiotis Danassis

Streaming and Matching Problems with Submodular Functions

Paritosh Garg

Anytime Heuristic for Weighted Matching Through Altruism-Inspired Behavior

Boi Faltings , Aris Filos Ratsikas , Panayiotis Danassis

Assignment and Matching

• Reference work entry
• Cite this reference work entry

• Dimitris Alevras 3  

1240 Accesses

3 Citations

Article Outline

Maximum Cardinality Bipartite Matching Problem

Weighted Bipartite Matching Problem

Weighted Matching Problem

Maximum Cardinality Matching Problem

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Subscribe and save.

• Get 10 units per month
• Download Article/Chapter or eBook
• 1 Unit = 1 Article or 1 Chapter
• Cancel anytime
• Available as PDF
• Read on any device
• Instant download
• Own it forever
• Durable hardcover edition
• Dispatched in 3 to 5 business days
• Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

The Distance Matching Problem

A Parameterized Study of Maximum Generalized Pattern Matching Problems

A Survey on Applications of Bipartite Graph Edit Distance

Ahuja R, Magnanti T, Orlin J (1994) Network flows. Wiley, New York

Google Scholar  

Alevras D (1997) Order preserving assignments without contiguity. Discret Math 163:1–11

MathSciNet   MATH   Google Scholar  

Ball MO, Derigs U (1983) An analysis of alternate strategies for implementing matching algorithms. Networks 13:517–549

Edmonds J (1965) Maximum matching and a polyhedron with (0, 1) vertices. J Res Nat Bureau Standards (B) 69B:125–130

MathSciNet   Google Scholar  

Edmonds J (1965) Paths, trees, and flowers. Canad J Math 17:449–467

Grötschel M, Holland O (1985) Solving matching problems with linear programming. Math Program 33:243–259

MATH   Google Scholar  

Grötschel M, Lovasz L, Schrijver A (1988) Geometric algorithms and combinatorial optimization. Springer, Berlin

Kuhn HW (1955) The Hungarian method for the assignment problem. Naval Res Logist Quart 2:83–97

Lovasz L, Plummer M (1986) Matching theory. North-Holland, Amsterdam

Micali S, Vazirani VV (1980) An O(√(|v|)|E|) algorithm for finding maximum matching in general graphs. IEEE Symp Found Computer Sci, pp 17–27

Nemhauser GL, Wolsey L (1988) Integer and combinatorial optimization. Wiley, New York

Padberg M, Alevras D (1994) Order-preserving assignments. Naval Res Logist 41:395–421

Padberg MW, Grötschel M (1985) Polyhedral theory. The Traveling Salesman Problem. Wiley, New York, pp 251–305

Padberg M, Rao MR (1982) Odd minimum cut-sets and b‑matchings. Math Oper Res 7:67–80

Pulleyblank WR (1989) Polyhedral combinatorics. Optimization, vol 1 of Handbook Oper Res and Management Sci. North-Holland, Amsterdam, pp 371–446

Download references

Author information

Authors and affiliations.

IBM Corporation, West Chester, USA

Dimitris Alevras

You can also search for this author in PubMed   Google Scholar

Editor information

Editors and affiliations.

Department of Chemical Engineering, Princeton University, Princeton, NJ, 08544-5263, USA

Christodoulos A. Floudas

Center for Applied Optimization, Department of Industrial and Systems Engineering, University of Florida, Gainesville, FL, 32611-6595, USA

Panos M. Pardalos

Rights and permissions

Reprints and permissions

Copyright information

© 2008 Springer-Verlag

About this entry

Cite this entry.

Alevras, D. (2008). Assignment and Matching . In: Floudas, C., Pardalos, P. (eds) Encyclopedia of Optimization. Springer, Boston, MA. https://doi.org/10.1007/978-0-387-74759-0_18

Download citation

DOI : https://doi.org/10.1007/978-0-387-74759-0_18

Publisher Name : Springer, Boston, MA

Print ISBN : 978-0-387-74758-3

Online ISBN : 978-0-387-74759-0

eBook Packages : Mathematics and Statistics Reference Module Computer Science and Engineering

Share this entry

Anyone you share the following link with will be able to read this content:

Sorry, a shareable link is not currently available for this article.

Provided by the Springer Nature SharedIt content-sharing initiative

• Publish with us

Policies and ethics

• Find a journal
• Track your research

Breadcrumbs Section. Click here to navigate to respective pages.

Solving Assignment Problem and Game Theory Using Graph Theory

DOI link for Solving Assignment Problem and Game Theory Using Graph Theory

Click here to navigate to parent product.

Graph theory aids as a mathematical model to signify any scheme confining a binary relation. In this paper, the Assignment problem and Game theory are solved in symmetric and non-symmetric problems using the Graph Theory approach. The method proposed in this work is a methodical process, apparent to implement for resolving assignment problems and Game theory problems in which so many routes of the path are possible to find the optimal solution in the directed graph and undirected graph in Graph theory. In this proposed work, the main graph is used to frame three other sub-graphs. Four routes of the path are taken in different ways in the graph. For each route, there is an in-degree and out-degree which frames the matrix representation. A numerical specimen is examined by means of a new technique in addition, the solution is computed by the existing two methods. Also, a performance comparison is made for the optimum solutions amongst this new method besides the two prevailing methods by means of Matlab. Using the graph theory, the solution to the assignment problem and game theory can be determined. The present work finally concludes the frame of the matrix of indegree and outdegree and also the results of the Assignment problem and game theory can be obtained.

• Privacy Policy
• Terms & Conditions
• Cookie Policy
• Taylor & Francis Online
• Taylor & Francis Group
• Students/Researchers
• Librarians/Institutions

Connect with us

Registered in England & Wales No. 3099067 5 Howick Place | London | SW1P 1WG © 2024 Informa UK Limited

Browse Course Material

Course info.

• Prof. Yufei Zhao

Departments

• Mathematics

As Taught In

• Applied Mathematics
• Discrete Mathematics
• Probability and Statistics

Learning Resource Types

Graph theory and additive combinatorics, 18.217 f2019 chapter 1: introduction to graph theory and additive combinatorics.

You are leaving MIT OpenCourseWare

Stack Exchange Network

Stack Exchange network consists of 183 Q&A communities including Stack Overflow , the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Q&A for work

Connect and share knowledge within a single location that is structured and easy to search.

Assignment problem with divisible tasks and hours

A general assignment problem is assigning a set of tasks(Ti) to a set of workers (Wi). Any agent can be assigned to perform any task, incurring some cost that may vary depending on the agent-task assignment. It is required to perform all tasks by assigning exactly one agent to each task and exactly one task to each agent in such a way that the total cost of the assignment is minimized.

Assignment problem table

For instance, Worker A can do Job1 in 9 hours, Job2 in 2 hours, Job3 in 7 hours and so on.

In my case, say Worker A has a total of 8 hours, can do 1/2 of Job1 in 3 hours, 1/4 of Job1 in 1/8 hours and so on, Worker B can do 1/3 of Job1 in 2 hours, 1/4 of Job2 in 5 hours similarly for other workers and job combinations. We need to assign fractional tasks to each of the workers so as to minimize the cost and maximize the task assignment.

• graph-theory
• bipartite-graphs
• matching-theory

• 1 $\begingroup$ What to solve for? What is asked? $\endgroup$ –  pooja somani Commented Sep 14, 2018 at 7:59
• $\begingroup$ Minimize the cost (number of hours), while maximizing the matching of persons with tasks $\endgroup$ –  Roh Codeur Commented Sep 14, 2018 at 8:37
• $\begingroup$ still appears unclear... $\endgroup$ –  pooja somani Commented Sep 14, 2018 at 8:41
• $\begingroup$ My apologies, I have updated the problem description $\endgroup$ –  Roh Codeur Commented Sep 14, 2018 at 9:25

You must log in to answer this question.

Browse other questions tagged graph-theory bipartite-graphs matching-theory ..

• Featured on Meta
• We've made changes to our Terms of Service & Privacy Policy - July 2024
• Bringing clarity to status tag usage on meta sites
• 2024 Community Moderator Election
• 2024 Election Results: Congratulations to our new moderator!

Hot Network Questions

• Difficulty understanding grammar in sentence
• Miracle Miracle Octad Generator Generator
• Chord definition misunderstanding
• Whether and when this sum will converge?
• "Knocking it out of the park" sports metaphor American English vs British English?
• Postdoc supervisor has stopped helping
• If physics can be reduced to mathematics (and thus to logic), does this mean that (physical) causation is ultimately reducible to implication?
• In the US, can I buy iPhone and Android phones and claim them as expense?
• Are Experimental Elixirs Magic Items?
• Did US troops insist on segregation in British pubs?
• Idiomatic alternative to “going to Canossa”
• What Christian ideas are found in the New Testament that are not found in the Old Testament?
• How did the cop infer from Uncle Aaron's statement that Miles has been visiting?
• Is there anything that stops the majority shareholder(s) from destroying company value?
• What is the difference between ‘coming to Jesus’ and ‘believing in Jesus’ in John 6:35
• Does gluing two points prevent simple connectedness?
• Why are the titles of certain types of works italicized?
• "apt install emacs" linuxmint22 requires a mail system
• Jacobi two square's theorem last step to conclusion
• Aftermarket stereo wiring help for 2012 chevy colorado WT
• What does 北渐 mean?
• How to justify a ban on exclusivist religions?
• Can figere come with a dative?
• What (if any) pre-breathes were "attempted" on the ISS, and why?

• Stack Overflow for Teams Where developers & technologists share private knowledge with coworkers
• Advertising & Talent Reach devs & technologists worldwide about your product, service or employer brand
• OverflowAI GenAI features for Teams
• OverflowAPI Train & fine-tune LLMs
• Labs The future of collective knowledge sharing
• About the company Visit the blog

Collectives™ on Stack Overflow

Find centralized, trusted content and collaborate around the technologies you use most.

Q&A for work

Connect and share knowledge within a single location that is structured and easy to search.

Get early access and see previews of new features.

solving the assignment problem for 3 groups instead of 2

Let's say we have 3 groups of people each one with n people, I need to assign them to n groups of triplets such that each triplet is made out of 1 person from the first group, one from the second and one from the third.

There's also a cost function for each possible triplet and we need to pair them in a way that would minimize the sum of the costs.

If there were only 2 groups than that would be the Assignment problem .

I thought of maybe using linear programming approach and give each triplet a variable and minimize the sum of weighted variables (according to the cost function) with the constraints that for each person the sum of the variables of the triplets his in would be 1 and each variable is between 0 and 1, but i'm not sure how to prove that there's an integer solution for that problem and if so how to find it.

• graph-theory
• linear-programming

• 1 This link seems to suggest that the problem is NP hard. –  hilberts_drinking_problem Commented Mar 31, 2020 at 1:02
• @hilberts_drinking_problem yes, I suspected that was the case. Kinda sucks, I wanted to use this for something related to building 3d-models from images but if it's NP-hard I guess it's impossible. –  Tomer Wolberg Commented Mar 31, 2020 at 1:46
• 1 I don't know much about this specific problem, but there may be some good heuristic approximations. Here is one paper that comes up in Google search. –  hilberts_drinking_problem Commented Mar 31, 2020 at 1:56
• @hilberts_drinking_problem Do you know if this paper proofs a constant approximation for the problem? i.e. if the total cost of the heuristic approximation algorithm is at most some constant multiplied by the optimal cost. I want to know that in order to know if it's worth it to purchase that 30$ paper. –  Tomer Wolberg Commented Apr 23, 2020 at 22:49
• 1 I quickly looked over the paper and it does not seem to provide a constant approximation result. They mostly focus on empirical performance of different combinations of heuristics. It might be a good idea to ask if such a bound is known on cstheory.stackexchange. You might also get better references. –  hilberts_drinking_problem Commented Apr 24, 2020 at 1:53

There seem to be many names for this problem: three-index assigment problem , 3-dimensional, or in general n-partite matching . Although the problem is NP-hard , as stated also in the comments above, moderately large instances can be solved quite efficiently using (M)ILP solvers.

Here is a 3-dimensional example using Python and PuLP. Moreover, the code can handle other dimensions n>=2 by adjusting the dimension list dims . Naturally, both problem and solution can be visualized as an n-partite network.

Your Answer

Reminder: Answers generated by artificial intelligence tools are not allowed on Stack Overflow. Learn more

Sign up or log in

Post as a guest.

Required, but never shown

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy .

Not the answer you're looking for? Browse other questions tagged graph-theory linear-programming or ask your own question .

• The Overflow Blog
• From PHP to JavaScript to Kubernetes: how one backend engineer evolved over time
• Featured on Meta
• We've made changes to our Terms of Service & Privacy Policy - July 2024
• Bringing clarity to status tag usage on meta sites
• Feedback requested: How do you use tag hover descriptions for curating and do...
• What does a new user need in a homepage experience on Stack Overflow?

Hot Network Questions

• How to calculate APR and amount owed
• Whether and when this sum will converge?
• Will this be the first time, that there are more People an ISS than seats in docked Spacecraft?
• When a submarine blows its ballast and rises, where did the energy for the ascent come from?
• On page 31 of ISL, why is the minimum possible test MSE over all methods (dashed line) 1 instead of another number?
• "Authorized ESTA After Incorrectly Answering Criminal Offense Question: What Should I Do?"
• Does gluing two points prevent simple connectedness?
• Are automorphisms of matrix algebras necessarily determinant preservers?
• Group automorphism fixing finite-index subgroup
• Vector of integers such that almost all dot products are positive
• How to justify a ban on exclusivist religions?
• How to extract code into library allowing changes without workflow overhead
• What is the difference between an `.iso` OS for a network and an `.iso` OS for CD?
• Name of engineering civil construction device for flattening tarmac
• If the Collatz conjecture is undecidable, then it is true
• "Knocking it out of the park" sports metaphor American English vs British English?
• Why are the titles of certain types of works italicized?
• Postdoc supervisor has stopped helping
• What is the lesson of the Book of Iyov for the "average" person
• How did the cop infer from Uncle Aaron's statement that Miles has been visiting?
• Visualizing histogram of data on unit circle?
• Should I GFCI-protect a bathroom light and fan?
• grep command fails with out-of-memory error
• Why does my Bluetooth speaker keep on connecting and disconnecting?

Bridging and Compressing Feature and Semantic Spaces for Robust Graph Neural Networks: An Information Theory Perspective

New citation alert added.

This alert has been successfully added and will be sent to:

You will be notified whenever a record that you have chosen has been cited.

To manage your alert preferences, click on the button below.

New Citation Alert!

Please log in to your account

Information & Contributors

Bibliometrics & citations, supplemental material, index terms.

Computing methodologies

Machine learning

Recommendations

Robust tensor graph convolutional networks via t-svd based graph augmentation.

Graph Neural Networks (GNNs) have exhibited their powerful ability of tackling nontrivial problems on graphs. However, as an extension of deep learning models to graphs, GNNs are vulnerable to noise or adversarial attacks due to the underlying ...

Towards Robust Graph Neural Networks for Noisy Graphs with Sparse Labels

Graph Neural Networks (GNNs) have shown their great ability in modeling graph structured data. However, real-world graphs usually contain structure noises and have limited labeled nodes. The performance of GNNs would drop significantly when trained on ...

Graph Structure Learning for Robust Graph Neural Networks

Graph Neural Networks (GNNs) are powerful tools in representation learning for graphs. However, recent studies show that GNNs are vulnerable to carefully-crafted perturbations, called adversarial attacks. Adversarial attacks can easily fool GNNs in ...

Information

Published in.

• General Chairs:

Northeastern University, USA

CENTAI / Eurecat, Italy

• SIGMOD: ACM Special Interest Group on Management of Data
• SIGKDD: ACM Special Interest Group on Knowledge Discovery in Data

Association for Computing Machinery

New York, NY, United States

Publication History

Permissions, check for updates, author tags.

• graph neural networks
• information theory
• semi-supervised learning
• Research-article

Funding Sources

• National Natural Science Foundation of China
• Funds for Scientific Research of Fujian Provincial Department of Finance
• Central Funds Guiding the Local Science and Technology Development
• Fujian Province Technology and Economy Integration Service Platform
• Fuzhou-Xiamen-Quanzhou National Independent Innovation Demonstration Zone Collaborative Innovation Platform

Acceptance Rates

Contributors, other metrics, bibliometrics, article metrics.

• 0 Total Citations
• 0 Total Downloads
• Downloads (Last 12 months) 0
• Downloads (Last 6 weeks) 0

View Options

Login options.

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

View options.

View or Download as a PDF file.

View online with eReader .

Share this Publication link

Copying failed.

Share on social media

Affiliations, export citations.

• Please download or close your previous search result export first before starting a new bulk export. Preview is not available. By clicking download, a status dialog will open to start the export process. The process may take a few minutes but once it finishes a file will be downloadable from your browser. You may continue to browse the DL while the export process is in progress. Download
• Download citation
• Copy citation

We are preparing your search results for download ...

We will inform you here when the file is ready.

Your file of search results citations is now ready.

Your search export query has expired. Please try again.