Note: You are looking at a static copy of the former PineWiki site, used for class notes by James Aspnes from 2003 to 2012. Many mathematical formulas are broken, and there are likely to be other bugs as well. These will most likely not be fixed. You may be able to find more up-to-date versions of some of these notes at http://www.cs.yale.edu/homes/aspnes/#classes.

1. Revenge of the Leptons

Construct a directed graph with nodes s, t, and x_ij for i=1..n and j=1..m. Create an edge with weight c_i1 from s to each node x_i1 and of weight +∞ from each node x_im to t. Create an edge with weight c_{i j+1} from each node x_ij to x_{i j+1} and an edge of weight s_ij from each node x_ij to each node x_{i+1 j} (treating n+1 as 1). Now find a minimum s-t cut on this graph, and set t_i to be the minimum j for which x_ij is on the t side of the cut.

Clearly this takes polynomial time. Does it work? The set S of nodes on the s side of the cut corresponds to bays that have not been cleaned out yet, while the set T of nodes on the t side correspond to those that have. The cost of the cut is the sum of

c_ij for each i and j = t_i, to pay for the edge between x_{i-1 j} and x_ij, plus
s_ij for each i and each j for which x_ij is in S and x_{i+1 j} is not; this corresponds to the cost of maintaining the force-field.

Since this is exactly the cost of the objective function in the problem, by minimizing it we minimize our cleaning cost.

2. A tripartite marriage problem

We'll have a variable yS for each triple S on the list, that is 1 if the triple is married and 0 otherwise. The linear program is