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.

29 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
4
votes
0answers
87 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 ...
3
votes
0answers
73 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 $...
3
votes
0answers
29 views

Moving objects onto a line segment so that their pairwise similarities are close to their pairwise distances on the line

I have some arbitrary pairwise similarity metric for some objects, and I am considering trying to find the best way to position the objects onto a line segment such that the pairwise euclidean ...
2
votes
0answers
16 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 ...
2
votes
0answers
42 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)$ ...
2
votes
0answers
42 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 ...
2
votes
0answers
187 views

Sub-optimal and fast solutions to assignment problem

I am looking for a fast solution to the assignment problem for large cost matrices (5000x5000 or larger). The Hungarian algorithm is $O^3$, which is impractical for any moderately large problem. Are ...
2
votes
0answers
129 views

How to construct a network flow problem?

I have the optimization problem given below max $\sum_{i=1}^{N}\sum_{j=1}^{M} x_{ij}R_{ij}$ s.t $\quad 1)\quad \sum_{j=1}^{M} x_{ij}=1 \quad \forall i$ $\quad 2)\quad x_{ij} \in {0,1}$ $\quad ...
2
votes
0answers
307 views

Assign $m$ tasks to $n$ workers, with $m \geq n$

There are $n$ students that share the same apartment. At each evening, one of them must prepare dinner for everyone. There are $m$ evenings to schedule, with $m \geq n$, and you have to assign any ...
2
votes
0answers
123 views

Subset minimizing the cost of a one-sided matching, involving preference orders

We're given a set of items $A=\{1,\dots,m\}$ and a set of people $B=\{1,\dots,n\}$. Each person has a preference ordering for the items in $A$. Each item in $A$ has a specific positive cost for each ...
2
votes
0answers
2k views

Job assignment problem

I want to solve job assignment problem using Hungarian algorithm of Kuhn and Munkres in case when matrix is not square. Namely we have more jobs than workers. In this case adding additional row is ...
1
vote
0answers
45 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 ...
1
vote
0answers
26 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 ...
1
vote
0answers
16 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 ? ...
1
vote
0answers
25 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 ...
1
vote
0answers
72 views

Task assignment problem with capabilities and time restrictions

I have the following optimalization problem. I use the notations below because maybe it would be easier to understand that way, but I'm not good at conventions – I'm not sure if I'm using it all the ...
1
vote
0answers
75 views

Hungarian algorithm to search over all matching?

I am working on the following problem- "Finding the matching among all possible matching such that the sum of edge weight is minimum in the matching." Please note that I like to search over all ...
1
vote
0answers
492 views

Optimal Preference Matching

I'm trying to find an algorithm that finds an optimal matching between $A$ and $B$, where each element $a$ of $A$ provides a preference order $\prec_a$ over $B$. I will notate the index of an element $...
1
vote
0answers
94 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 ...
1
vote
0answers
241 views

What needs to be done after deleting an item in a hash table built under opening addressing with linear probing

In some textbook problems, the problem asks me to insert a bunch of elements and remove a bunch of elements. Insertion is done using linear probing, i.e. h = XmodR + I, when there is a collision, I ...
0
votes
0answers
28 views

How to find the optimal assignment using the Kuhn-Munkres algorithm?

I managed to get through the Wikipedia article until the last step and I have implemented an algorithm that can reach the optimum. Unfortunately the article does not say anything about how can I make ...
0
votes
0answers
21 views

Algorithm for this generalized assignment problem

I'm trying to find an algorithm for the following problem. There are $5$ computer files with capacity $18$, $23$, $12$, $125$, $45$ MB respectively and there are $4$ hard disks with capacity $25$, $...
0
votes
0answers
65 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, ...
0
votes
0answers
36 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 ...
0
votes
0answers
227 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 ...
0
votes
0answers
70 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 ...
0
votes
0answers
815 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'...
0
votes
0answers
98 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 ...
0
votes
1answer
395 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 ...