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.
0
votes
0answers
35 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
15 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, ...
1
vote
0answers
19 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
49 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
82 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
39 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 ...
0
votes
1answer
68 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
31 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
47 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 ...
4
votes
1answer
240 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 ...
1
vote
2answers
236 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 ...
3
votes
1answer
93 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 ...
0
votes
1answer
82 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 ...
0
votes
2answers
89 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 ...
2
votes
1answer
288 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 ...
2
votes
0answers
48 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 ...
3
votes
1answer
61 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 ...
3
votes
1answer
439 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.
...
1
vote
0answers
276 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
335 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
91 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
201 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
0answers
57 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 ...
0
votes
1answer
2k 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 ...
0
votes
1answer
245 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 ...
4
votes
2answers
122 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 ...
3
votes
2answers
290 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 ...
1
vote
2answers
175 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 ...
0
votes
0answers
683 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'...
4
votes
1answer
328 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 ...
1
vote
1answer
307 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 ...
0
votes
0answers
89 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 ...
1
vote
1answer
247 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 ...
6
votes
2answers
87 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 ...
2
votes
1answer
480 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 ...
4
votes
2answers
242 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 ...
2
votes
2answers
1k views
How to match two sets of points based on the closeset distance?
I have a set of points (tiny triangles) $K=\{1,2,\ldots, k\}$ and a set points (tiny circles) $N=\{1,2,\ldots, n\}$ and a matrix of positive real values $\mathbf{D}=\left[d_{ij}\right]$ for all $i\in ...
2
votes
0answers
106 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 ...
0
votes
2answers
166 views
Minimizing the overall cost over groups
I am trying to solve the problem of minimizing the overall cost over several groups. The schema of the data goes something like this:
...
1
vote
1answer
4k views
Seating arrangement problem
$n$ professors go to a conference and have to sit together at a table. See illustration below for $n=8$
Each professor has people they like to sit next to and people they do not want to sit next ...
1
vote
1answer
290 views
Match students and teachers based on ranking
I have a similar question to that of Stable Marriage Problem.
This is the criteria1) 1 Student must have 1 Teacher only.2) 1 Teacher ideally should have 3-4 Students.
The spreadsheet is done using ...
2
votes
0answers
27 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 ...
1
vote
0answers
245 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 ...
1
vote
2answers
584 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
2k views
Algorithm for a list of best solutions to the Assignment problem
I am trying to brute force a classical substitution cipher. The problem is that there are $26!$ possible keys. So, I'd like to do frequency analysis to try likely keys first. Then, on the first $n$ ...
2
votes
0answers
116 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 ...
3
votes
2answers
638 views
What is the appropriate algorithm for bipartite matching with constraints?
I have a problem that is a bit complex, and I don't know what method/model I should use to express it (much less solve it).
Let's say we have a lot of employees and a few jobs to be done. Each ...
1
vote
1answer
135 views
What makes an MILP problem solvable?
Knapsack problems, Assignment problems can all be expressed as (MILP) mixed integer linear programs. MILP is NP-complete. But Knapsack problem is solvable in pseudo-polynomial time using dynamic ...
1
vote
1answer
94 views
Matching a set of paths to an incrementally generated graph
I am working on an approximate matching problem, where I have a set of paths in an unknown graph (A) and a partial graph (B), where B is generated incrementally during the matching process (and can be ...
2
votes
2answers
72 views
$k$-gifts problem
Consider the following problem:
Suppose you have $k$ nephews and $d$ dollars in your pocket all of which you need to spend. Given a set of $n$ toys with different prices, find whether there exists $...
