How to find the highest number of changes/permutations inside a group (maybe a graph)

user_8286346 0
Viewed 52

Lets say in my company there are a number N of workers and M sectors. Each worker is currently assigned to a sector, also each worker is all willing to change to another sector.

For example:

Worker A is in sector 1 but want to go to sector 2
B is in 2 but want 3
C is in 3 but want 2
D is in 1 but want 3
and so on...

But they all must change with eachother.

A go to B position and B go to A position

or

A go to B position / B go to C position / C go to A position

I know that not everyone will change sectors, but I'm wondering if there is any specific algorithm that could find what movements will yield the maximum amount of changes.

I tought about naively swap two workers but some of them may be missing, they could all form a "loop" and no one would be left out (if possible)

I could use Monte Carlo to chain the workers and find the longest chain/loop but that would be too expensive as N and M grows

Also tought about finding the longest path in a graph using djikstra but as it looks like a NP-hard problem

Does anyone know an algorithm or how could I solve this efficiently? Or I'm trying to fly too close to the sun here?

graph-theory algorithm
2 Answers

This can be solved as a min-cost circulation problem. Construct a flow network where each sector corresponds to a node, and each worker corresponds to an arc. The capacity of each arc is 1, and the cost is −1 (i.e., we should move workers if we can). The conservation of flow constraint ensures that we can decompose the worker movements into a sum of simple cycles.

Klein's cycle canceling algorithm is not the most efficient, but it's very simple. Use (e.g.) Bellman−Ford to find a negative-cost cycle in the network, if one exists. If so, reverse the direction of each arc in the cycle, multiply the cost of each arc in the cycle by −1, and loop back to the beginning.

user_21446690

You could use the following observations to generate the most attractive sector changes (measured as how many workers get the change they want). In order of falling attractiveness,

  1. Identify all circular chains of sector changes. Everybody gets the change they want.
  2. Identify all non-circular chains of sector changes. They can be made circular at the expense of one worker not getting what s/he wants.
  3. Revisit 1. Combine any two circular chains at the expense of two workers not getting what they want.

Instead of one optimal solution, you get a list of many more or less attractive options. You will have to put some bounds on steps 1 - 3 to keep options down to a tractable number.

Admin1
Related