Homework 12

CS409 - Spring 2000

Due: Thursday, May 4

1. (15 points) Dating Problem [from Ahuja, Magnati, Orlin 1993].  A dating service receives data from p men and p women.  These data determine what pairs of men and women are mutually compatible.  Since the dating service's commission is proportional to the number of dates it arranges, it would like to determine the maximum number of compatible couples that can be formed.  Explain how to formulate this problem as a matching problem.  (Note that each man or women is assigned at most one date.)

    

2. (15 points) Seat Sharing Problem [from Ahuja, Magnati, Orlin 1993].  Several families are planning a shared car trip on scenic drives in New Hampshire's White Mountains.  To minimize the possibility of any quarrels, they want to assign individuals to cars so that no two members of a family are in the same car.  Explain how to formulate this problem as a network flow problem. (Hint: the people are the "flow"; make sure you have the right number of people per family and the right number of people per car.)

    

3. (10 points) Consider the following flow network.
   1. What is the value of the maximum flow from s to t?
   2. Describe which edges are part of the minimum cut.