jpgmoreira's blog

By jpgmoreira, history, 5 weeks ago, In English,

Hi, I'm studying about the minimum-cost flow problem, but I got a little confused because I found two different definitions to this problem.

1) From the definition found here, there is no source or sink nodes in the flow network. Each node has a number bi called the supply value of the node, such that if bi > 0 the node is a supply node, and if bi < 0 node is a demand node. The objective is then to find a flow association to the arcs, such that the constraints posed are respected, and the total cost of the flow is minimized.

2) From definition found here however, there is one source and one sink nodes, and no supply values to nodes as above. The objective is, from the set of all maximum flows from source to sink, find one that has the minimum total cost.

I would like to get some help also to clarify if the "Min-cost flow" and "Min-cost Max-flow" are two different problems, or if those are just two names to a same problem.

Thanks.

 
 
 
 
  • Vote: I like it
  • -1
  • Vote: I do not like it

»
5 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

I suggest you to read the chapter about flows in Algorithm Design, by Tardos and Kleinberg. In there they show that by solving the min cost flow problem, one can also solve problems 01 and 02.