I'm trying to design an algorithm for the following generalized assignment problem. We converted the problem to a weighted bipartite graph constituted of two sets $A$ and $B$ where $|A| \ne |B|$. Any edge in $A$ has a size and an edge in $B$ has a capacity which means an edge in $B$ can accept more input vertices up to its maximum capacity. $C$ is the cost vector; $C_{ij}$ is the cost of a vertex from edge $i$ in $A$ to edge $j$ in $B$. The target is a minimum cost perfect matching. That is all edges in $A$ require matching with an edge in $B$ as long as the sum of vertices coming to an edge in $B$ does not exceed its capacity.

As the solution, I see min-cost flow networks can be solved by converting to a Ford-Fulkerson problem, but I see such problems are normally seeking for max flow targets, not min cost. Should I modify the Ford-Fulkerson to follow my problem and how? I am happy to hear about alternative solutions as well.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.