Skip to main content
added 359 characters in body
Source Link

CertainlyIf you are requiring the flow to be a max-flow, this approach is valid; the max-flow at the min-cost of the transformed network must correspond to the max-flow at the max-cost of the original network. The max-cost flow has to be a max-flow, because any augmenting path would increase the cost. So you can just run a min-cost algorithm on the transformed network with the required flow being the max-flow.

The only question is if the min-cost algorithm you want to use can handle negative edge costs. For what it's work, the Wikipedia article on Minimum-Cost Flow states that "most minimum-cost flow algorithms supporting edges with negative costs."

But for this approach to be valid, you must require the max-cost flow to be a max-flow, because it is not true that max-cost flows will always be max-flows. Imagine a network where it is more costly for flow to travel along some cycle, which blocks any flow from getting from the source to the sink. So then calling min-cost max-flow on the transformed network will not give the correct answer.

Certainly this approach is valid; the max-flow at the min-cost of the transformed network must correspond to the max-flow at the max-cost of the original network. The max-cost flow has to be a max-flow, because any augmenting path would increase the cost. So run a min-cost algorithm on the transformed network with the required flow being the max-flow.

The only question is if the min-cost algorithm you want to use can handle negative edge costs. For what it's work, the Wikipedia article on Minimum-Cost Flow states that "most minimum-cost flow algorithms supporting edges with negative costs."

If you are requiring the flow to be a max-flow, this approach is valid; the max-flow at the min-cost of the transformed network must correspond to the max-flow at the max-cost of the original network. So you can just run a min-cost algorithm on the transformed network with the required flow being the max-flow.

The only question is if the min-cost algorithm you want to use can handle negative edge costs. For what it's work, the Wikipedia article on Minimum-Cost Flow states that "most minimum-cost flow algorithms supporting edges with negative costs."

But for this approach to be valid, you must require the max-cost flow to be a max-flow, because it is not true that max-cost flows will always be max-flows. Imagine a network where it is more costly for flow to travel along some cycle, which blocks any flow from getting from the source to the sink. So then calling min-cost max-flow on the transformed network will not give the correct answer.

Post Undeleted by Maxwell Allman
Post Deleted by Maxwell Allman
Source Link

Certainly this approach is valid; the max-flow at the min-cost of the transformed network must correspond to the max-flow at the max-cost of the original network. The max-cost flow has to be a max-flow, because any augmenting path would increase the cost. So run a min-cost algorithm on the transformed network with the required flow being the max-flow.

The only question is if the min-cost algorithm you want to use can handle negative edge costs. For what it's work, the Wikipedia article on Minimum-Cost Flow states that "most minimum-cost flow algorithms supporting edges with negative costs."