Questions tagged [assignment-problem]
For questions about the assignment problem in combinatorial optimization, NOT for problems that you've been set as a homework assignment.
127 questions
- Bountied 0
- Unanswered
- Frequent
- Score
- Trending
- Week
- Month
- Unanswered (my tags)
2
votes
1
answer
47
views
Maximum cardinality matching with a priority order
Problem Setup
Let's say we have a bipartite graph $(U, V)$ where the nodes of the graph are labelled with a positive integer and each edge $(u_i, v_i)$ has $u_i < v_i$. Our goal is to find a ...
3
votes
1
answer
127
views
Assignment problem with dependencies between assignments
I've been working on a simulator for my grid based game in order to find optimal solutions. One heuristic I'm using to prune the search space is the distance to goals. There are n players and m goals ...
1
vote
0
answers
64
views
Can the group-structure of my constraint reduce the corresponding assignment problem to polynomial time search complexity?
Consider a finite Abelian group $G$ where each element is its own inverse. As an explicit example, let $G$ be the integers 0 to 31 under the bitwise XOR $\oplus$ operation. We have a collection of $n$ ...
2
votes
1
answer
268
views
Assignment problem, but minimise the greatest individual cost, rather than the aggregate cost
https://en.wikipedia.org/wiki/Hungarian_algorithm
In the assignment problem as described above, the goal is to find an assignment that minimizes the total cost, and the Hungarian Algoirthm is a ...
2
votes
1
answer
75
views
Finding a perfect matching that minimizes a cycle weight
We are given a complete bipartite graph with positive weights on the edges (as in the assignment problem). Initially, all edges are directed from left to right, as in this example:
We have to compute ...
0
votes
1
answer
141
views
Is there a non-NP-hard algorithm for solving the task assignment problem for workers
input: A set of n n workers and a set of m m tasks.
Each worker has: Available working time (in hours). A set of skills (at least one, possibly more).
Each task has: Execution duration (in hours). ...
1
vote
0
answers
100
views
Subquadratic algorithms for approximate graph matching of two undirected trees
I am searching for efficient algorithms to optimize the approximate graph matching (AGM) problem. The general case of this problem is known to be NP-hard (equivalent to the quadratic assignment ...
2
votes
2
answers
311
views
Solving the "Reverse" Assignment Problem with an Added Constraint?
Note: This is a continuation of my previous question, found here
As written, my previous question was too unconstrained: @BaderAbuRadi showed that depending on the $C$ chosen, there can be multiple ...
2
votes
2
answers
336
views
Solving the "reverse" Assignment Problem?
According to Wikipedia, the assignment problem can be formally defined as:
Given two sets, A and T, together with a weight function $C : A \times T \to R$. Find a bijection $f : A \to T$ such that ...
2
votes
2
answers
100
views
Auction algorithm for assignment problem with "singles"
Consider the following variant of the assignment problem. There are $I$ men and $J$ women. Each man can stay single or be assigned to a woman, and vice versa. Each potential match has value $u_{ij}$. ...
1
vote
1
answer
97
views
How can I assign people to groups of 4 and optimize for "strangers" on a week-to-week basis when the group can change?
Let's say I have a group of people that meets every week. I would like to assign them to groups of 4. How can I assign these people such that, week after week, collectively, every group consists ...
1
vote
1
answer
98
views
Can you identify this assignment problem and efficient solutions or estimates?
Problem Statement
My wife's business runs a summer camp for 68 students. The students are divided
into cabins:
27 students in 3 groups of 7 and one group of 6 belong in one set of 4 cabins;
41 ...
0
votes
0
answers
50
views
Distribute work minimizing
You have n types work items. Each work item must be distributed to at least m processors. There are k processors (n > k > ...
1
vote
0
answers
60
views
Lower bounds on max-flow and assignment problems
As far as I know, all existing strongly polynomial algorithms for flows and assignment problem have $\Omega(V^3)$ complexity in the arithmetic model (assuming the graph is dense). I'm interested in ...
1
vote
0
answers
58
views
Find an assignment discarding a subset of possible assignments
We have a $N \times N$ cost matrix where the cost denotes the amount incurred for assigning a worker to a task.
The number of possible assignments is $N!$. Let us call this set of all possible ...