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