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.
101
questions
0
votes
1
answer
36
views
What is this task type?
There are people and the food they prefer:
John -20> Apple
John -10> Pear
Ethan -20> Apple
Ethan -5> Orange
Michael -10> Pear
Michael -10> Limon
The numbers indicate how strongly ...
- 33
3
votes
1
answer
56
views
variant of assignment problem with overload penalties instead of constraints
I want to assign $m$ tasks to $n$ workers where $m>n$, so as to minimize assignment costs defined by an $m \times n$ matrix $C$. That is, I want to find Boolean variables $x_{i,j}$ which minimize
$$...
- 78
0
votes
1
answer
48
views
How to prove that the generalized assignment problem (GAP) is NP-hard?
Specifically, what NP-hard problem can we reduce (the decisions version of) GAP to and how do we prove its correctness?
The decision version of the generalized assignment problem is to determine ...
- 1
2
votes
0
answers
46
views
Finding a simple algorithm for an assignment problem
I have an assignment problem where I need to assign resources to consumers. Each consumer has a list of resources it'd like to acquire, ordered by preference, and each consumer can have at most one ...
- 121
2
votes
0
answers
52
views
Min Cost Max Flow algorithms for providing multiple solutions
Minimum Cost Maximum Flow algorithms have been known to provide an optimal flow routing for network flow problems in satisfactory runtime. Some of the algorithms for solving a min-cost max-flow ...
- 21
0
votes
1
answer
45
views
Expected behavior in the min max random assignment problem
Consider the standard assignment problem: $n$ people are assigned to n jobs (one person to one job) so to minimize the sum of costs. When the costs are generated randomly (using the exponential (1) ...
- 171
0
votes
1
answer
80
views
Min max solution to the random assignment problem
Consider the standard assignment problem: $n$ people are assigned to $n$ jobs (one person to one job) so to minimize the sum of costs. When the costs are generated randomly (using the exponential (1) ...
- 171
1
vote
1
answer
69
views
Variant of assignment problem
This is something like assignment problem, we have 2 group of people, first contains $n$ person and second contains $m$ person. we have a matrix $C$ which is an $n \times m$ matrix and our goal is to ...
- 11
2
votes
0
answers
89
views
Assignment Problem with Minimum and Maximum constraints [duplicate]
I have the following problem:
In a school, there are n students and m clubs, with n > m. Each student needs to be assigned a club. The students have preferences, (say top 3 or top 5) of the clubs ...
- 275
2
votes
0
answers
146
views
The max-min resource assignment problem
I am wondering if there are any results for the following max-min assignment problem:
Given $n$ machines $C = \{C_1, C_2, \dots, n\}$ with the $k$-th machine has power $C_k$. There are $m$ tasks $T = \...
- 21
1
vote
0
answers
49
views
Is n-dimentional assignment problem for points NP-hard?
We have $n$ sets of $k$ points in $\mathbb R^d$ and we are trying to partition them to $k$ clusters of $n$ points such that from each set every point is mapped to a different cluster and the sum of ...
- 136
1
vote
0
answers
50
views
Algorithms for alignment of posets
I have been looking for a while but I cannot find an algorithm for a particular generalisation of sequence alignment.
I have two posets $(A, <)$ and $(B, <)$ and a similarity score $s(a, b)$ for ...
- 111
1
vote
0
answers
36
views
Find approximate 'best' matching pairs by calculating the fewest possible weights
My specific problem is as follows:
Given two list of texts (in the order of 5 to 50 items)
Find best matching pairs with their corresponding matching score (weight)
Where each item can only be ...
- 111
1
vote
1
answer
23
views
Predicate variant of Assignment Problem
Given two equally sized sets, $P$ of Boolean predicates and $E$, I want to decide if there exists a bijective function $f: P \rightarrow E$, such that
\begin{align}
\forall p \in P \; p(f(p))
\end{...
- 113
1
vote
1
answer
42
views
Fair assignment of storage for multiple writers (load balance)
I'm trying to optimize a system with a better algorithm for allocating storage. The system has 'N' writer processes and 'M' disks. (N < 30, M < 10. N can change, M is constant).
Any process can ...
- 111
2
votes
0
answers
28
views
Hungarian method: seemingly different algorithms from different sources?
When I look online for examples of the Hungarian method for solving the min-weight assignment problem, for example here, it involves iterating on the cost matrix; subtracting entries from the rows and ...
- 305
0
votes
1
answer
340
views
Algorithm for assigning people to groups
Given a list $L = [1, 2, .., n]$ and a list $C = [(L_i, L_j), ....]$ form a group of pairs $G = g_1, ..., g_{n/2}$ such that:
every element of $L$ is assigned to exactly one group
$g_k = (L_i, L_j) \...
- 371
2
votes
0
answers
48
views
Randomized Assignment Problem
Given $x_1,...,x_n,y_1,...,y_n\in \mathbb{R}^d$ find a permutation matrix $P\in\mathbb{S}_d$ that minimizes $\sum_{ij}P_{ij}|x_i-y_j|$.
This is an assignment problem and can be solved in $O(n^3+n^2d)$ ...
1
vote
0
answers
17
views
Assignment Problem with Non assignable cell
I have question for you guys. In this question is there something else that I should do ? When i try to solve with the way that my professor thought , its unsolveable. What should i do to solve this ?
...
- 11
0
votes
0
answers
76
views
Special case of stable marriage
I have an instance of the stable marriage problem in which the first side $S_1$ has $n_1$ agents and the second side $S_2$ has $n_2$ agents with $n_2$ is very big in comparison to $n_1$. In addition, ...
- 385
4
votes
1
answer
192
views
Minimizing total distance traveled by points in points cloud transformation
I have a point cloud of size n (in the example on picture n = 5). The starting coordinates are in green, destination coordinates are in red. What I need is to move the points from the starting ...
- 93
5
votes
1
answer
241
views
Maximum flow on a tripartite graph
I have to solve an assignment problem between $\{1,\dots, N\}$ agents and $\{1,\dots, M\}$ objects, which comes to maximize :
\begin{equation}
\sum_{ij}\beta_{ij}x_{ij}
\end{equation}
where $x_{ij}$ ...
- 51
2
votes
1
answer
138
views
Assignment problem or something else?
My primary goal with this question is to identify the type of problem I have so I know what solution to pursue. I think it's either an instance of the assignment problem or the fair item allocation ...
- 123
0
votes
0
answers
57
views
Algorithm for dual sided matching problem
Is the an algorithm that would help solve this problem:
Teams are swapping members.
Each team has preferences for members it 'wants' from other teams.
Each member has preferences for the teams its ...
- 9
4
votes
0
answers
116
views
Assign n people to m rooms of different sizes, such that noone is alone
I'm looking for an efficient way to assign n people to m rooms in a very specific way.
INPUT:
The program receives two sets of people (set of males and set of females), as well as a set of available ...
- 141
3
votes
1
answer
164
views
Assignment Problem -- finding the $k$ agents with the best assignment
I have a question that I have been thinking about. Suppose we have $n$ agents, $m$ tasks, a cost matrix with $M_{ij}$ being the cost of agent $i$ performing task $j$, and are given a value $k \leq n$. ...
- 61
3
votes
0
answers
98
views
Assignment problem with symmetric matrix
I came across a problem which I think can be reduced to the assignment problem/Hungarian algorithm.
We have matrix $A$ and matrix $B$ which are both $n\times n$ symmetric matrices. We can rearrange $...
- 61
1
vote
1
answer
55
views
Grouping n points into groups of size m with objective to have least traveling distance in each group
Assumptions:
There are "n" jobs which are distributed over the city.
Company has "k" available workers.
Each worker can do "x" jobs per day.
"x" is dependent to the worker skills and the distance ...
2
votes
0
answers
50
views
Explain this Graph Matching solved in Linear Time
I'm interested in a better explanation about the paper Computing Optimal Assignments in Linear Time for Approximate Graph Matching.
The graph edit distance is approximated by assignments in linear ...
- 139
3
votes
1
answer
33
views
Choosing which workers (limited number) to use in a binary assignment problem?
First of all, I am not completely sure whether this problem belong to the category of assignment problems so feel free to correct me in this case.
The problem:
We are given a set of $m$ workers $A = ...
- 43
1
vote
1
answer
649
views
How to cover given entries in a matrix with minimum number of rows and columns?
We have a matrix of 0 and 1. We want to cover all the 1's. We can cover a raw or a column with a plate. We want to use the minimum number of plates.
example
0 0 1 0
0 1 0 1
0 0 1 0
0 0 1 0
...
- 103
0
votes
0
answers
379
views
Is this variation of the assignment problem NP-hard, and does it have a name?
I’m trying to solve a problem very similar to the assignment problem, with a few twists.
The problem has a certain amount of workers, and a certain amount of tasks - workers is always >= tasks. Each ...
- 11
1
vote
1
answer
106
views
Problem class of assigning N persons to N tasks, zero costs with prefs
I am looking for the general problem class / computational complexity / algorithms for the following problem:
N tasks must be accomplished by N persons. 1 task to be done by exactly 1 person and vice ...
- 113
0
votes
0
answers
108
views
What is the most efficient way to solve a workshop scheduling problem?
I am trying to design an algorithm to solve a workshop scheduling problem.
The problem is as follows:
I have to schedule a workshop consisting of a finite number of time slots, and a finite number of ...
- 101
1
vote
1
answer
82
views
Algorithm to assign producers to consumers with respect to connections
I am trying to analyze supply chains in a game and have come across this problem:
First, an informal description: I have producers and consumers. Each producer produces a certain amount of goods, ...
- 113
1
vote
0
answers
29
views
Optimal matching of individuals in vehicles
I am looking for an algorithm to find the optimal matching/allocation of n individuals in m identical vehicles. The aim is to create groups of individuals who will share these vehicles. Groups' size ...
- 11
1
vote
1
answer
57
views
find separate pairs of points with minimal total distance
I am looking for suitable algorithm how to solve the following problem.
For finite set $S \subset \mathbb{R}$ ($|S| = N_{S}$) we need to find its disjunctive separation $S = A \cup B$ ($A \cap B = \...
2
votes
0
answers
219
views
Sub-optimal and fast solutions to assignment problem
I am looking for a fast solution to the assignment problem for large cost matrices (5000x5000 or larger). The Hungarian algorithm is $O^3$, which is impractical for any moderately large problem.
Are ...
- 21
1
vote
1
answer
124
views
Matching schedules between users and providers
I have a problem I've been dealing for the past few days, and I'm pretty stuck.
Each user has a schedule for a given week, such as ...
- 48
1
vote
1
answer
402
views
Difference between stable marriage problem and assignment problem
What is the difference between the stable marriage problem and an assignment problem? Both refer to a matching problem in general but what is their specific difference?
I can see clear differences in ...
- 113
1
vote
0
answers
75
views
Task assignment problem with capabilities and time restrictions
I have the following optimalization problem. I use the notations below because maybe it would be easier to understand that way, but I'm not good at conventions – I'm not sure if I'm using it all the ...
- 111
1
vote
0
answers
81
views
Hungarian algorithm to search over all matching?
I am working on the following problem-
"Finding the matching among all possible matching such that the sum of edge weight is minimum in the matching."
Please note that I like to search over all ...
- 11
5
votes
1
answer
902
views
Maximizing the sum of selected elements in a matrix
I’m trying to find an efficient algorithm for the following optimization problem:
Given a matrix $A$ with elements $a_{ij}$ and dimension $k$, select exactly $n$ elements from $A$ ($n<k$) such ...
- 51
2
votes
2
answers
456
views
How to solve this very complicated assignment problem
A set of m items need to be placed into n stacks, where m > n. Each stack has z positions. An item has different widths when placed into different positions in a stack. The width of an item depends ...
- 21
3
votes
1
answer
192
views
Students in classroom problem - Flow in network
I have room, which is opened some days in week, in different hours each day.
I have multiple students, each has time some days in week, in different hours.
Each student have to visit the room ...
- 31
0
votes
1
answer
124
views
Efficient traffic allocation
Users can be assigned to one experiment on my site. I have an API that developers use to trigger logic for each experiment. They call ExperimentEngine.run() to trigger the code logic for the ...
- 103
0
votes
2
answers
189
views
Reduction from an assignment problem to an independent set problem: NP-hard
The problem I have is as follows:
I have a complete bipartite graph $G=(V \cup C,E)$ as input, where $|V|=1, |C|=n, |E|=n$
The interpretation is that the node of $V$ is a vehicle, the $n$ nodes of C ...
- 11
2
votes
1
answer
676
views
Bipartite Perfect Matching "Assignment Problem" - finding an assignment of a particular weight
The assignment problem is to find the minimum weight perfect matching in a weighted bipartite graph. This problem can be solved using the Hungarian algorithm in polynomial time. It is also possible to ...
- 73
2
votes
0
answers
129
views
How to sum vectors to maximize magnitude? [duplicate]
There are $n$ vectors, represented as $(d_x, d_y)$ pairs. Someone stands at point $(0, 0)$ of infinite euclidean grid. For every vector he can either move by $d_x$ in $x$ axis and $d_y$ in $y$ axis or ...
- 143
3
votes
1
answer
76
views
affinity based static load balancing
I am trying to find a good model the following problem:
Given a collection of work packets x, y, z, ..., and a collection of worker nodes ...
- 133