JOIN
Get Time
forums   
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat (newest first)  | Threaded  | Tree
Previous Thread  |  Next Thread
How we can solve this problems? | Reply
Suppose that a minimum cost flow problem cost vector c and capacity vector u is solved optimally, and the optimal solution is x*. Suppose further that the optimal set of node potentials is y*.
a) If the capacity of one of the arcs is increased by 1, show how to find the new optimal solution (x and y vector) by solving a shortest path problem. Clearly state the shortest path problem, and how to modify the solution as a result of the shortest path found.
b) Suppose instead of the change in part a), the cost of one of the arcs is increased by 1. Show how to find the new optimal solution (x and y vector) by solving a max flow problem. Clearly state the max flow problem, and how to modify the solution as a result of it.
RSS