Select one problem from the list below, or propose your own problem, with approval.
Work with up to 1 other person. Turn in one solution per group.
Use the ideas we discuss in class, such as for testing to see if a team can still win its division by the end of the season.
Clearly describe the way you will convert the problem into a network flow problem. Define all of your notation.
Illustrate your construction with at least one, hopefully more examples. Try to make the examples interesting -- such as for the winning team problem a situation in which it is a close matter as to whether the team will win the division.
Take the "Application" section with a large grain of salt. For those of you that quickly solve the above steps, you can consider this part. For those of you who need more time to solve the above steps, you can skip this part.
You can take liberties with the problem if there is a reasonable justification -- just don't change the problem to make it trivially true.
If you haven't made progress by Wednesday, 12/7, I will need to meet with you on Wednesday afternoon.
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.