JOIN
 Select a Forum     Round Tables New Member Discussions News Discussions Algorithm Matches Marathon Matches NASA Tournament Lab TopCoder Cookbook High School Matches Sponsor Discussions Development Forums Design Forums Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings View: Flat (newest first)  | Threaded  | Tree Previous Thread  |  Next Thread Forums Tutorial Discussions Minimum Cost Flow (Article | Article (Part 2) | Article (Part 3)) How we can solve this problems?
 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.
 Forums Tutorial Discussions Minimum Cost Flow (Article | Article (Part 2) | Article (Part 3)) How we can solve this problems? Previous Thread  |  Next Thread