I am not a computer science theorist, but think this real world problem belongs here.The problemMy 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    DestinationMaria              1  ->  2Marcos             2  ->  3Jones              3  ->  4Terry              4  ->  5Joe                5  ->  6Rodrigo            6  ->  1Barbara            6  ->  1Marylin            1  ->  4Brown              4  ->  6Benjamin           1  ->  3Lucas              4  ->  1The 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 The goalHaving collected all the requests, how to satisfy most of them?Theory(?) applicationHaving 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).The questionIf this problem is expressed asHow 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.
How to find the cycles which, together, involve the biggest number of non-shared edges in a directed graph?
ds.algorithms;graph algorithms;application of theory
OK, I read the code of TradeMaximizer and I believe it solves the following, more general problem.PROBLEM: Given is a directed graph whose arcs have costs. Find a set of vertex-disjoint cycles that maximizes the number of covered vertices first, and minimizes the total cost second.To solve the question asked here, make the vertices be employees and draw an arc $x\to y$ of unit cost when $x$ would like the job of $y$. Note that employees are now vertices rather than edges. The nice thing is that an employee can say I really want the job of $y$, but that of $z$ would do too.Solution:Build a bipartite graph as follows: For each vertex $x$ in the original graph introduce a left vertex $x_L$, a right vertex $x_R$, and an arc $x_L\to x_R$ whose cost is huge (bigger than the sum of costs in the original graph). For each arc $x\to y$ in the original graph, introduce an arc $x_L\to y_R$ in the bipartite graph.Find a minimum cost perfect matching in the bipartite graph.There is some preprocessing of the original graph too: Remove arcs between SCCs, then process all SCCs of size $>1$ as indicated above.(In fact, TradeMaximizer iterates over all optimal solutions, according to the two criteria above, in order to heuristically optimize other things, such as the length of the biggest cycle. Big cycles increase the chance of a deal not going thru because one person changes their mind.)PS: The author, Chris Okasaki, confirmed that this is what the code does, back at the blog post.