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
0answers
44 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
25 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
1answer
18 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{...
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, ...
1
vote
1answer
33 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 ...
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 ...
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 ...
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 ...
0
votes
1answer
46 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) \...
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
3answers
5k views

How can I solve this constrained assignment problem?

The assignment problem is defined as follows: There are a number of agents and a number of tasks. Any agent can be assigned to perform any task, incurring some cost that may vary depending on ...
5
votes
1answer
122 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}$ ...
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 ? ...
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$, $...
4
votes
1answer
133 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 ...
2
votes
1answer
95 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 ...
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
1answer
35 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 ...
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
1answer
122 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$. ...
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 $...
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 ...
3
votes
1answer
23 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 = ...
1
vote
1answer
362 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 ...
0
votes
0answers
226 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 ...
1
vote
1answer
55 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 ...
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 ...
1
vote
1answer
38 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, ...
3
votes
1answer
138 views

Students in classroom problem - Flow in network

I have room, which is opened some days in week, in different hours each day. I have multiple students, each has time some days in week, in different hours. Each student have to visit the room ...
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
1answer
53 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 = \...
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 ...
1
vote
1answer
87 views

Matching schedules between users and providers

I have a problem I've been dealing for the past few days, and I'm pretty stuck. Each user has a schedule for a given week, such as ...
1
vote
1answer
227 views

Difference between stable marriage problem and assignment problem

What is the difference between the stable marriage problem and an assignment problem? Both refer to a matching problem in general but what is their specific difference? I can see clear differences in ...
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 ...
2
votes
1answer
480 views

Bipartite Perfect Matching “Assignment Problem” - finding an assignment of a particular weight

The assignment problem is to find the minimum weight perfect matching in a weighted bipartite graph. This problem can be solved using the Hungarian algorithm in polynomial time. It is also possible to ...
1
vote
1answer
251 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 ...
0
votes
2answers
126 views

Reduction from an assignment problem to an independent set problem: NP-hard

The problem I have is as follows: I have a complete bipartite graph $G=(V \cup C,E)$ as input, where $|V|=1, |C|=n, |E|=n$ The interpretation is that the node of $V$ is a vehicle, the $n$ nodes of C ...
5
votes
1answer
674 views

Maximizing the sum of selected elements in a matrix

I’m trying to find an efficient algorithm for the following optimization problem: Given a matrix $A$ with elements $a_{ij}$ and dimension $k$, select exactly $n$ elements from $A$ ($n<k$) such ...
2
votes
2answers
393 views

How to solve this very complicated assignment problem

A set of m items need to be placed into n stacks, where m > n. Each stack has z positions. An item has different widths when placed into different positions in a stack. The width of an item depends ...
0
votes
1answer
123 views

Efficient traffic allocation

Users can be assigned to one experiment on my site. I have an API that developers use to trigger logic for each experiment. They call ExperimentEngine.run() to trigger the code logic for the ...
3
votes
1answer
865 views

Assignment Problem - multiple tasks, but only one chosen based on their preference (cost)

I've looked at Hungarian algorithm and Knapsack problems and neither quite hit the nail on the head. I've been trying to best rephrase my question while searching for answers and haven't got anywhere. ...
2
votes
0answers
108 views

How to sum vectors to maximize magnitude? [duplicate]

There are $n$ vectors, represented as $(d_x, d_y)$ pairs. Someone stands at point $(0, 0)$ of infinite euclidean grid. For every vector he can either move by $d_x$ in $x$ axis and $d_y$ in $y$ axis or ...
1
vote
2answers
941 views

How to solve an optimization problem that deals with the optimal combination of given ratios?

I'm volunteering for a non-profit, and was asked to write a program for this problem, but I'm having a little trouble tackling it. Here's the problem: So they're a daycare, and they get paid by the ...
3
votes
1answer
73 views

affinity based static load balancing

I am trying to find a good model the following problem: Given a collection of work packets x, y, z, ..., and a collection of worker nodes ...
1
vote
0answers
491 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
1answer
848 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 ...
3
votes
2answers
115 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: ...
4
votes
1answer
207 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 ...
1
vote
2answers
203 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 ...