0
$\begingroup$

I have a question concerning the use of the Ford-Fulkerson algorithm. Since a minimum cost flow problem is a linear programming problem, it has a dual problem. That dual would be to maximize a certain function. Considering this, is it possible to apply the Ford-Fulkerson algorithm to that dual in order to solve the minimum cost flow problem?

$\endgroup$
0
$\begingroup$

No. Ford-Fulkerson cannot be used to solve arbitrary linear programming instances. It can only solve instances that are in the form of "max flow in this flow graph". The dual doesn't have that form.

The dual is to find the minimum cut. A standard way to find the minimum cut is by finding the max flow, and then using the max-flow min-cut theorem.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.