# 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
Filter by
Sorted by
Tagged with
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 ...
56 views

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
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 ...
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
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 ...
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
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
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 ...
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
146 views

• 371
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
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 ? ...
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
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
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 : $$\sum_{ij}\beta_{ij}x_{ij}$$ where $x_{ij}$ ...
• 51
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
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 ...
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
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$. ...
98 views

• 43
1 vote
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
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
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
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
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
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
57 views

• 143