0
$\begingroup$

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.

$\endgroup$
1

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.