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

117 questions
Filter by
Sorted by
Tagged with
33 views

### How can I assign people to groups of 4 and optimize for "strangers" on a week-to-week basis when the group can change?

Let's say I have a group of people that meets every week. I would like to assign them to groups of 4. How can I assign these people such that, week after week, collectively, every group consists ...
• 101
1 vote
41 views

### Can you identify this assignment problem and efficient solutions or estimates?

Problem Statement My wife's business runs a summer camp for 68 students. The students are divided into cabins: 27 students in 3 groups of 7 and one group of 6 belong in one set of 4 cabins; 41 ...
24 views

### Distribute work minimizing

You have n types work items. Each work item must be distributed to at least m processors. There are k processors (n > k > ...
• 101
1 vote
34 views

### Lower bounds on max-flow and assignment problems

As far as I know, all existing strongly polynomial algorithms for flows and assignment problem have $\Omega(V^3)$ complexity in the arithmetic model (assuming the graph is dense). I'm interested in ...
• 11
1 vote
32 views

### Find an assignment discarding a subset of possible assignments

We have a $N \times N$ cost matrix where the cost denotes the amount incurred for assigning a worker to a task. The number of possible assignments is $N!$. Let us call this set of all possible ...
• 11
66 views

### Number of matchings in a bipartite graph having missing edges

Suppose we have a bipartite graph with $N$ vertices on either side. In the full bipartite graph, the number of edges is $N^2$ and the number of possible matchings (i.e. assignments) is $N!$. Now ...
• 11
1 vote
123 views

### High-multiplicity maximum-weight matching

There are $n$ people and $m$ jobs. We would like to assign at most one job to each person. For each person,job pair, there is a positive value determining the fitness of this person to that job. The ...
• 6,070
138 views

### Best balanced assignment

I'm at a problem I don't know better to name it... maybe it's already a well known problem? It seems quite simple: There are objects and labels in a n:m relation. (Each of the n objects may be ...
1 vote
117 views

### Preference based assignment problem to maximize utility

I am studying an optimization problem which can be recast as an LP I have described below. I wish to understand the structure of optimizers of the original problem by studying the optimizers of the LP....
• 11
74 views

### How an assignment problem is solved using greedy heuristic algorithm

Consider small instance of GAP involving 5 items and 2 resources with capacities 5 and 12 respectively. If we have cost matrix Cij and also consumption matrix bij with jobs vs resources, how can we ...
56 views

### Assignment problem with maximal partitioning

Recently I came across a problem I don't get may hands on: Given p binary positions. Let s be the number of "set-bits" (1 < s < p * 2^(p-1) - 1). I need the maximal set of assigments ...
1 vote
245 views

### Algorithm for a modified worker-task assignment problem with groups of tasks and substitutability between tasks within groups

I'm looking for an algorithm to solve a modified version of the assignment problem. It differs from the standard assignment problem in that the modified version has groups of tasks instead of just ...
• 13
1 vote
69 views

### A kind of generalised assignment problem where we minimise error relative to a goal "weight"/"value" - how to solve it?

I apologize if I did not use the terminology entirely correctly in the title. This problem seems to me quite similar to an assignment problem and likely something that occurs in real life in business. ...
• 13
1 vote
42 views

### Assign items from inventory to people maxmizing the number of satisfied people

We have a set of people, and each person has a list of wished items (not unique, they could want multiple copies of each item). We have an inventory of items that we want to assign to the people. We ...
• 111
1 vote
478 views

### fastest algorithm for rectangular linear assignment problem

I want to optimally assign $m$ jobs equally to $n$ workers, where $m>n$. Assume $m = an$ for some integer $a$, so that each worker must get exactly $a$ jobs. (The rectangular linear assignment ...
• 90
1 vote
62 views

• 21
1 vote
51 views

### Is n-dimentional assignment problem for points NP-hard?

We have $n$ sets of $k$ points in $\mathbb R^d$ and we are trying to partition them to $k$ clusters of $n$ points such that from each set every point is mapped to a different cluster and the sum of ...
1 vote
61 views

### Algorithms for alignment of posets

I have been looking for a while but I cannot find an algorithm for a particular generalisation of sequence alignment. I have two posets $(A, <)$ and $(B, <)$ and a similarity score $s(a, b)$ for ...
• 111
1 vote
44 views

### Find approximate 'best' matching pairs by calculating the fewest possible weights

My specific problem is as follows: Given two list of texts (in the order of 5 to 50 items) Find best matching pairs with their corresponding matching score (weight) Where each item can only be ...
• 111
1 vote
26 views

### Predicate variant of Assignment Problem

Given two equally sized sets, $P$ of Boolean predicates and $E$, I want to decide if there exists a bijective function $f: P \rightarrow E$, such that \begin{align} \forall p \in P \; p(f(p)) \end{...
• 113
1 vote
45 views

### Fair assignment of storage for multiple writers (load balance)

I'm trying to optimize a system with a better algorithm for allocating storage. The system has 'N' writer processes and 'M' disks. (N < 30, M < 10. N can change, M is constant). Any process can ...
• 111
74 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 ...
• 377
810 views

1 vote
104 views

### Grouping n points into groups of size m with objective to have least traveling distance in each group

Assumptions: There are "n" jobs which are distributed over the city. Company has "k" available workers. Each worker can do "x" jobs per day. "x" is dependent to the worker skills and the distance ...
52 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 ...
• 177
59 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 = ...
• 43
419 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
149 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