Flow Network Capacity Augmentation (1 Viewer)

Users Who Are Viewing This Thread (Users: 0, Guests: 1)

315
1
Suppose that you have a http://en.wikipedia.org/wiki/Flow_network" [Broken] with integer edge capacities, and n dollars. You may spend one dollar to increase the capacity of an existing edge by one. The question is, how can you spend your dollars so that the maximum flow through the resulting network is maximized?
 
Last edited by a moderator:
525
5
Suppose that you have a http://en.wikipedia.org/wiki/Flow_network" [Broken] with integer edge capacities, and n dollars. You may spend one dollar to increase the capacity of an existing edge by one. The question is, how can you spend your dollars so that the maximum flow through the resulting network is maximized?
The max-flow min-cut theorem might be a good place to start in constructing a spending strategy.
 
Last edited by a moderator:

The Physics Forums Way

We Value Quality
• Topics based on mainstream science
• Proper English grammar and spelling
We Value Civility
• Positive and compassionate attitudes
• Patience while debating
We Value Productivity
• Disciplined to remain on-topic
• Recognition of own weaknesses
• Solo and co-op problem solving
Top