Min Cost Max Flow 0-1 Version

Revision en1, by scopeInfinity, 2017-03-26 13:31:22

For a general Min Cost Max Flow problem cost C associated to an edge having flow F results in C*F .

Thus Objective is to minimize Sigma Ci * Fi, where Fi <= Capacity of ith Edge and giving maximum flow.

0-1 Version

If we have a variation that with a flow F <= Capacity is flowing through an edge only Ci cost should be considered NOT Ci*Fi.

i.e. If edge allows flows its going to cost C or else its going to cost 0.

I am not sure, How can I proceed for it. The optimal cost flow is not required.

Tags max flow, min cost flow, #graph, discrete

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English scopeInfinity 2017-03-26 13:31:22 597 Initial revision (published)