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
10
votes
1
answer
2k
views
Assignment problem for multiple days
I have a problem that can be reduced to an assignment problem.
(In a previous question i found out how to do that.)
Which means we have a set $A$ of agents and a set $T$ of tasks as well as a cost ...
- 609
8
votes
4
answers
1k
views
XOR-like behavior in flow networks
XOR is not the correct name, but I am looking for some kind of exclusive behavior.
I am currently solving a set of different (assignment) problems by modeling flow networks and running a min-cost-max-...
- 609
7
votes
2
answers
127
views
CNF form of variable assignment problem
There are n variables $x_1$, $x_2$,..., $x_n$ and each one of them takes values from 1 to k (k>= n) and all are distinct. How can I represent this in the CNF form? (I tried the trivial way of trying ...
- 85
6
votes
2
answers
1k
views
A variant of the Assignment Problem
In my variant of the assignment problem I have a set $A$ of agents and a set (of possibly different cardinality) $T$ of tasks. Each agent needs to be assigned exactly $n$ or $n+1$ tasks, and each task ...
- 241
5
votes
1
answer
906
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
5
votes
1
answer
635
views
Heuristic algorithms for the dense assignment problem
Given a dense assignment problem ($n$ tasks assigned to $n$ workers, where each worker can do any one of the tasks), I understand the best complexity is $O(n^3)$, using the Hungarian Algorithm or ...
- 398
5
votes
1
answer
2k
views
Simple Task-Assignment Problem
I have this simple 'assignment' problem:
We have a set of agents $A = \{a_1, a_2, \dotso, a_n\}$ and set of tasks $T= \{t_1, t_2, \dotso, t_m\}$. Note that $m$ is not necessarily equal to $n$. Unlike ...
- 270
5
votes
1
answer
243
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
4
votes
2
answers
219
views
Discrete assignment problem with penalties
I came across a problem were you have to plan an optimal assignment pattern. Let's say you have $j=1,\ldots,n$ tasks during $i=1,\ldots,m$ time periods.
It's an single agent problem where we have to ...
- 143
4
votes
2
answers
401
views
Working Optimization Algorithm
This is my basic setup: I have five time slots (A, B, C, D, E; each day has these five time slots) over 60 days that all need to be filled with n people each (n must remain a variable). However, each ...
- 143
4
votes
1
answer
4k
views
Stable marriage problem with only one side having preferences [duplicate]
I was wondering about a variation on the Stable Marriage Problem. Initially, we have two sets of entities, usually males and females, and they have preference lists ranking the other group, and ...
- 143
4
votes
1
answer
194
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
4
votes
1
answer
210
views
How do solve assignment of one interval to another?
Is there an efficient algorithm for the following problem?
Input: Set of holes and pegs. Each hole/peg is an interval $[\ell,u]$ with integer endpoints.
Question: Can all the holes be filled ...
user75291
4
votes
1
answer
426
views
Assignment problem with no cost
I have a problem that I was able to conceptualize as following:
Problem
We have a set of n people. And m subsets representing their ethnicity like White, Hispanic, Asian etc. Given any combination of ...
- 41
4
votes
0
answers
119
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
2
answers
2k
views
How to match two sets of points based on the closeset distance?
I have a set of points (tiny triangles) $K=\{1,2,\ldots, k\}$ and a set points (tiny circles) $N=\{1,2,\ldots, n\}$ and a matrix of positive real values $\mathbf{D}=\left[d_{ij}\right]$ for all $i\in ...
- 338
3
votes
2
answers
139
views
Algorithm for arranging elements into different sized buckets
I have a set of items. For each item, there is a list of buyers I can sell it to and a corresponding price they will pay me. For example:
...
- 133
3
votes
2
answers
77
views
$k$-gifts problem
Consider the following problem:
Suppose you have $k$ nephews and $d$ dollars in your pocket all of which you need to spend. Given a set of $n$ toys with different prices, find whether there exists $...
- 203
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
1
answer
57
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
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
3
votes
2
answers
455
views
Optimality in multi-agent multi-target path finding
Suppose I have a regular rectangular weighted grid with multiple agents and obstacles. Agents cannot be in grid sites that contain obstacles, and for simplicity assume multiple agents can be in the ...
- 131
3
votes
1
answer
2k
views
Algorithm for a list of best solutions to the Assignment problem
I am trying to brute force a classical substitution cipher. The problem is that there are $26!$ possible keys. So, I'd like to do frequency analysis to try likely keys first. Then, on the first $n$ ...
user23039
3
votes
2
answers
1k
views
What is the appropriate algorithm for bipartite matching with constraints?
I have a problem that is a bit complex, and I don't know what method/model I should use to express it (much less solve it).
Let's say we have a lot of employees and a few jobs to be done. Each ...
- 31
3
votes
1
answer
650
views
A variant of job assignment (scheduling) problem with variable time span
The problem is a scheduling problem with n jobs and k machines. Each job i can be started at any time, but its duration is not exactly known except a time span interval. For example, a job may take ...
- 31
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
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
3
votes
1
answer
1k
views
Assignment Problem - multiple tasks, but only one chosen based on their preference (cost)
I've looked at Hungarian algorithm and Knapsack problems and neither quite hit the nail on the head. I've been trying to best rephrase my question while searching for answers and haven't got anywhere.
...
- 31
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
3
votes
0
answers
30
views
Moving objects onto a line segment so that their pairwise similarities are close to their pairwise distances on the line
I have some arbitrary pairwise similarity metric for some objects, and I am considering trying to find the best way to position the objects onto a line segment such that the pairwise euclidean ...
- 209
2
votes
3
answers
6k
views
How can I solve this constrained assignment problem?
The assignment problem is defined as follows:
There are 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 ...
- 123
2
votes
1
answer
7k
views
Seating arrangement problem
$n$ professors go to a conference and have to sit together at a table. See illustration below for $n=8$
Each professor has people they like to sit next to and people they do not want to sit next ...
- 155
2
votes
2
answers
459
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
2
votes
1
answer
888
views
Polynomial time solution for bipartite matching
Inspired by this StackOverflow question, I am wondering if there is an efficient algorithm for the following problem:
Assume $n$ items and $n$ boxes, with all boxes numbered numerically and all ...
- 201
2
votes
1
answer
102
views
Choice of algorithm for hierarchical clustering for minimizing network communication costs
Suppose I have a large distributed task running on a cluster system where part of the workload is compute bound and part depends on network performance. Data transfer is not completely homogeneous ...
- 123
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
2
votes
1
answer
687
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
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
57
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
2
votes
0
answers
95
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
147
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
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
2
votes
0
answers
50
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)$ ...
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 ...
- 137
2
votes
0
answers
221
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
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
2
votes
0
answers
140
views
How to construct a network flow problem?
I have the optimization problem given below
max $\sum_{i=1}^{N}\sum_{j=1}^{M} x_{ij}R_{ij}$
s.t
$\quad 1)\quad \sum_{j=1}^{M} x_{ij}=1 \quad \forall i$
$\quad 2)\quad x_{ij} \in {0,1}$
$\quad ...
- 41
2
votes
0
answers
419
views
Assign $m$ tasks to $n$ workers, with $m \geq n$
There are $n$ students that share the same apartment. At each evening, one of them must prepare dinner for everyone. There are $m$ evenings to schedule, with $m \geq n$, and you have to assign any ...
- 302
2
votes
0
answers
127
views
Subset minimizing the cost of a one-sided matching, involving preference orders
We're given a set of items $A=\{1,\dots,m\}$ and a set of people $B=\{1,\dots,n\}$. Each person has a preference ordering for the items in $A$. Each item in $A$ has a specific positive cost for each ...
- 33
2
votes
0
answers
2k
views
Job assignment problem
I want to solve job assignment problem using Hungarian algorithm of Kuhn and Munkres in case when matrix is not square. Namely we have more jobs than workers.
In this case adding additional row is ...
- 173