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
1 vote
0 answers
25 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 ...
akhil's user avatar
  • 11
0 votes
1 answer
41 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 ...
akhil's user avatar
  • 11
1 vote
1 answer
93 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 ...
Erel Segal-Halevi's user avatar
0 votes
1 answer
132 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 ...
User42's user avatar
  • 1
1 vote
0 answers
100 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....
Reema's user avatar
  • 11
0 votes
0 answers
27 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 ...
Sai chand Gogisetty's user avatar
0 votes
1 answer
48 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 ...
User42's user avatar
  • 1
0 votes
0 answers
42 views

Assignment problem - One task per agent, with restriction

I have $k$ agents and 2 tasks. Each agent is to be assigned to one task. Thus, agent $i$ must choose between tasks 1 and 2, which have costs $c_i$ and $b_i$ and flow $p_1(c_i)$ and $p_2(b_i)$, ...
Otni's user avatar
  • 1
1 vote
1 answer
145 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 ...
DOS's user avatar
  • 13
1 vote
1 answer
59 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. ...
edwi's user avatar
  • 11
1 vote
1 answer
35 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 ...
mdatsev's user avatar
  • 111
1 vote
1 answer
264 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 ...
ludog's user avatar
  • 90
1 vote
2 answers
61 views

Given a sequence of sets, choose one element from each to get the lowest number of changes

Let $k,n \in \mathbb{N} $ and non empty sets $X_1, X_2, \dots, X_n \subseteq \{1,2,\dots,k\}$. Define the change counting cost function $f: X_1 \times X_2 \times \dots \times X_n \to \mathbb{N}$ by $f(...
Aladin's user avatar
  • 113
2 votes
0 answers
47 views

Balanced Assignment Problem with updatable cost

I have a problem that can be reduced to an assignment problem. (this is related to some cryptography problems) Which means we have a set $A$ of $n$ agents and an equal size set $T$ of tasks as well as ...
SRichoux's user avatar
0 votes
1 answer
41 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 ...
user51515151's user avatar
3 votes
1 answer
81 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 $$...
ludog's user avatar
  • 90
0 votes
1 answer
223 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 ...
Joe Mac's user avatar
2 votes
0 answers
57 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 ...
Jay Lemmon's user avatar
2 votes
0 answers
106 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 ...
kfertakis's user avatar
0 votes
1 answer
65 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) ...
fox's user avatar
  • 183
0 votes
1 answer
160 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) ...
fox's user avatar
  • 183
1 vote
1 answer
99 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 ...
blueDanube's user avatar
2 votes
0 answers
155 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 ...
devam_04's user avatar
  • 285
2 votes
0 answers
150 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 = \...
ybk1996's user avatar
  • 21
1 vote
0 answers
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 ...
Tomer Wolberg's user avatar
1 vote
0 answers
58 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 ...
Epimetheus's user avatar
1 vote
0 answers
43 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 ...
de1's user avatar
  • 111
1 vote
1 answer
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{...
Jonas Nyrup's user avatar
1 vote
1 answer
44 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 ...
Danny's user avatar
  • 111
2 votes
0 answers
31 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 ...
Rohit Pandey's user avatar
0 votes
1 answer
669 views

Algorithm for assigning people to groups

Given a list $L = [1, 2, .., n]$ and a list $C = [(L_i, L_j), ....]$ form a group of pairs $G = g_1, ..., g_{n/2}$ such that: every element of $L$ is assigned to exactly one group $g_k = (L_i, L_j) \...
Alex5207's user avatar
  • 371
2 votes
0 answers
56 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)$ ...
Alexander Mathiasen's user avatar
1 vote
0 answers
18 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 ? ...
Fatih Can's user avatar
0 votes
0 answers
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, ...
Farah Mind's user avatar
4 votes
1 answer
290 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 ...
eawer's user avatar
  • 103
5 votes
1 answer
365 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}$ ...
deb2014's user avatar
  • 51
2 votes
1 answer
177 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 ...
tmoore82's user avatar
  • 123
0 votes
0 answers
58 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 ...
hkman's user avatar
  • 9
4 votes
0 answers
179 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 ...
leller's user avatar
  • 141
3 votes
1 answer
181 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$. ...
user89692's user avatar
3 votes
0 answers
126 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 $...
user89692's user avatar
1 vote
1 answer
94 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 ...
Ajand Mardalizad's user avatar
2 votes
0 answers
51 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 ...
R. S.'s user avatar
  • 137
3 votes
1 answer
55 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 = ...
grescha's user avatar
  • 43
0 votes
0 answers
401 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 ...
Illorum's user avatar
  • 11
1 vote
1 answer
141 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 ...
bliako's user avatar
  • 113
0 votes
0 answers
134 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 ...
JohnDoe's user avatar
  • 101
1 vote
1 answer
130 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, ...
jalgames's user avatar
  • 113
1 vote
0 answers
31 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 ...
ColineB's user avatar
  • 11
1 vote
1 answer
60 views

find separate pairs of points with minimal total distance

I am looking for suitable algorithm how to solve the following problem. For finite set $S \subset \mathbb{R}$ ($|S| = N_{S}$) we need to find its disjunctive separation $S = A \cup B$ ($A \cap B = \...
michalkvasnicka's user avatar