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.
89
questions
10
votes
1answer
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 ...
8
votes
4answers
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-...
7
votes
2answers
110 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 ...
6
votes
2answers
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 ...
5
votes
1answer
641 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 ...
5
votes
1answer
527 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 ...
5
votes
1answer
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 ...
5
votes
1answer
122 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}$ ...
4
votes
2answers
166 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 ...
4
votes
2answers
317 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 ...
4
votes
1answer
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 ...
4
votes
1answer
123 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 ...
4
votes
1answer
138 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 ...
4
votes
1answer
207 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 ...
4
votes
1answer
405 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 ...
4
votes
0answers
87 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 ...
3
votes
2answers
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 ...
3
votes
2answers
115 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:
...
3
votes
1answer
117 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$. ...
3
votes
1answer
73 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 ...
3
votes
2answers
404 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 ...
3
votes
1answer
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$ ...
3
votes
2answers
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 ...
3
votes
1answer
597 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 ...
3
votes
1answer
23 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 = ...
3
votes
1answer
849 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.
...
3
votes
0answers
68 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 $...
3
votes
0answers
29 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 ...
2
votes
1answer
6k 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 ...
2
votes
3answers
5k 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 ...
2
votes
1answer
710 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 ...
2
votes
2answers
74 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 $...
2
votes
1answer
81 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 ...
2
votes
1answer
92 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 ...
2
votes
0answers
16 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 ...
2
votes
0answers
42 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
0answers
42 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 ...
2
votes
0answers
183 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 ...
2
votes
1answer
468 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 ...
2
votes
0answers
107 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 ...
2
votes
0answers
128 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 ...
2
votes
0answers
305 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 ...
2
votes
0answers
123 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 ...
2
votes
0answers
1k 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 ...
1
vote
2answers
387 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 ...
1
vote
1answer
358 views
An algorithm to find the maximum profitable assignment
Given a set of workers $w_1,...,w_m$ and and a set of tasks $t_1,...,t_n$, and a $m\times n$ matrix $P$ s.t. $P(i,j)$ is the profit of assigning worker $i$ to task $j$. One worker can only be ...
1
vote
1answer
145 views
What makes an MILP problem solvable?
Knapsack problems, Assignment problems can all be expressed as (MILP) mixed integer linear programs. MILP is NP-complete. But Knapsack problem is solvable in pseudo-polynomial time using dynamic ...
1
vote
1answer
313 views
Hungarian Assignment Algorithm Implementation
I want to implement the "vertex similarity" algorithm described in the paper Graph Isomorphism Detection Using Vertex Similarity Measure. The algorithm is as follows:
...
1
vote
1answer
346 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
...
1
vote
1answer
36 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, ...
