Final Math 454 Homework, Due 12/9/05

Project Parameters

A word on minimum cost flow

Minimum cost (maximum) flow means to assign a cost C(e) to each arc in the network, and compute the total cost of the flow in the network as
                    cost = (sum over all arcs e) C(e)*f(e)
(Recall that f(e) is the flow on arc e, and c(e) (lowercase c) is the capacity on arc e.)  Minimum cost flow simply means to find, over all possible maximum flows, the one with minimum cost.  Sometimes this is referred to as the Min cost max flow problem, or sometimes just the min cost flow problem.  If you choose a problem involving minimum cost flow, it should be clear where the costs are coming from.  You don't have to provide an algorithm which actually finds the min cost flow.  Usually you can start with any max flow and look for ways of redirecting flows around cycles in order to reduce the cost without changing the value of the flow.  But in general this is a linear programming problem, and not entirely trivial.

  1. Eulerian Tours (by reversing arcs).
  2. Eulerian Tours (by duplicating arcs).
  3. Minimum Cost Messenger Problem.
  4. Aircraft Maintenance.
  5. Non-Parallel Job Processing.

Back to Math 454 class page.