I'm taking a grad level algorithms course and we just ended the course talking about linear programming, and we had previously talked about the max flow/min cut problem. Our professor said that the max flow/min cut problem can be formulated as an LP problem.

I asked the professor what the non feasible but locally optimal points in the LP formulation of the max flow/min cut problem correspond to in the max flow/min cut problem (more so the max flow part, I think he said the dual problem was min cut and we talked a little bit about what feasible points in the min cut problem were), but he couldn't think of the answer off the top of his head.

I was wondering if anyone here knew.



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.