# 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.

82 questions
Filter by
Sorted by
Tagged with
99 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 ...
65 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}$ ...
67 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 ...
23 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 ...
67 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 ...
61 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$. ...
42 views

9 views

### How to assign people to categories based on some voting rules?

Say in an election there are predefined categories users can be assigned to. Of the people who are assigned to a certain category, other users can vote for them. To compute the results, the following ...
128 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 ...
89 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 ...
25 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 ...
48 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 ...
24 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, ...
23 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 ...
51 views

561 views

### Matching with One-sided Preferences

I'm dealing with a slight variation on a classic matching problem on sets $A$ and $B$), where: Set $A$ has an incomplete set of preferences (not all of $B$ is included) Set $B$ has no preferences ...
106 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: ...
203 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 ...
65 views

### Assignment problem for compute mininum weight cycle cover?

I've read in multiple articles and books that the computation of a cycle cover for a given graph is possible in polynomial time, since this problem can be viewed as the assignment problem, which is a ...
3k views

### Is there a greedy algorithm to solve the assignment problem?

The assignment problem is defined as: There are n people who need to be assigned to n jobs, one person per job. The cost that would accrue if the ith person is assigned to the jth job is a known ...
343 views

### Given a list of students and their courses, place them in specific classes

I could use some help coming up with the best way to solve this problem. I've been curious as to how something like this would work, as the worst case seems way too bad. Problem Given a group of ...
135 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 ...
352 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 ...
186 views

### Selecting best crew combination that meets requirements of a variety of jobs

I am developing an application, which performs combinatorial function as described below. Could anyone point out a suitable algorithm (or direction)? == Basic scheme: == There are fixed amount of ...
753 views

### Minimum cost perfect matching (Using General graph

This is a continuation of the problem described in this topic: Optimized algorithm to match entities together based on heuristics. I've come a little closer as to what might be the best solution. I'...
430 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 ...
331 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 ...
93 views

### Job Scheduling: Two Resources, Defined Job Length, Defined Earliest Start

Problem I stumbled over the following job scheduling problem. There are two resources, for simplicity I call them ... CPU_RAM (MAX_CPU_RAM specifies what is available in total) GPU_RAM (MAX_GPU_RAM ...
249 views

### How can I assign cooks to customers?

I haven't done much algorithm writing till now. I have a specific scenario and I am wondering which approach shall I take. Scenario: Let us suppose that we have 4 guys (A,B,C,D) We want to ...
101 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 ...
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 ...