I am not a computer science theorist, but think this real world problem belongs here.
My company have several units accross the country.
We offered to employees the possibility to work on another unit. But there is a condition: The total number of workers on a unit cannot change.
That means: We'll allow a employee to left his unit if someone wants his place.
Example (ficticious) request data:
Name Origin Destination Maria 1 -> 2 Marcos 2 -> 3 Jones 3 -> 4 Terry 4 -> 5 Joe 5 -> 6 Rodrigo 6 -> 1 Barbara 6 -> 1 Marylin 1 -> 4 Brown 4 -> 6 Benjamin 1 -> 3 Lucas 4 -> 1
The above, plotted:
See how we have to choose between the red, blue or black options?
The real problem is a little more complex, because we have 27 units and 751 requests. Please take a look at the visualization
Having collected all the requests, how to satisfy most of them?
Having graph $G(V, E)$, let every unit be a vertex $V$ and a request be a directed edge $E$, a successful exchange will take the form of a directed cyle.
Each cycle must use $E$ only once (a worker cannot leave his unit twice), but can visit $V$ several times (a unit can have many workers wanting to leave).
If this problem is expressed as
"How to find the cycles which, together, involve the biggest number of non-shared edges in a directed graph"?
Will we satisfy most of the requesters?
That being true, there is an algorithm to find that optimal set of cycles?
Will this greddy approach solve the problem?
- Find the biggest directed cycle on $G$;
- Remove it's edges from $G$;
- Repeat 1 until there is not a directed cycle on $G$;
Can you help me?
Do you know another way to describe the original problem (making most of requesters happy)?
Edit: changed department to unit, to better describe the problem.