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 xij for i=1..n and j=1..m. Create an edge with weight ci1 from s to each node xi1 and of weight +∞ from each node xim to t. Create an edge with weight ci j+1 from each node xij to xi j+1 and an edge of weight sij from each node xij to each node xi+1 j (treating n+1 as 1). Now find a minimum s-t cut on this graph, and set ti to be the minimum j for which xij 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

• cij for each i and j = ti, to pay for the edge between xi-1 j and xij, plus

• sij for each i and each j for which xij is in S and xi+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

2014-06-17 11:58