# Questions tagged [assignment-problem]

For questions about the [assignment problem](https://en.wikipedia.org/wiki/Assignment_problem) in combinatorial optimization, **not** for problems that you've been set as a homework assignment.

79 questions
Filter by
Sorted by
Tagged with
33 views

### Assign n people to m rooms of different sizes, such that noone is alone and people are in largest rooms possible

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

### How to clear rows in Tetris? [closed]

I'm doing an java assignment on tetris and this little bit of code is giving me trouble. I can't seem to figure out why my code for clearing completed lines is not working. Can some one please help me ...
50 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$. ...
38 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 ...
77 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 ...
64 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 ...
24 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 ...
44 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 ...
20 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, ...
22 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 ...
50 views

492 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 ...
103 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: ...
202 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 ...
311 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 ...
129 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 ...
332 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 ...
182 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 ...
725 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'...
406 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 ...
325 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 ...
90 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 ...
248 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 ...
93 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 ...
571 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 ...
269 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 ...