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.

Filter by
Sorted by
Tagged with
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 ...
user avatar
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-...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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}$ ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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: ...
user avatar
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 $...
user avatar
  • 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$. ...
user avatar
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 $$...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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$ ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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 = ...
user avatar
  • 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 ...
user avatar
  • 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. ...
user avatar
  • 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 $...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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 = \...
user avatar
  • 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 ...
user avatar
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)$ ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 173