/Discuss this assignment. /Solutions are available.

1. Revenge of the Leptons

The insidious Leptons from CS365/Assignments/HW08 have sent replacements: the even more insidious Reptons. As before, each of the cargo bays 1..n of the Orbitex Space Station is infested with some number of Reptons, which are so hideously repulsive that the station can only be saved by eliminating them completely. Unfortunately, the cost of eliminating a bay full of Reptons varies considerably depending on the stage they are at in their breeding cycle, so there may be an incentive to delay wiping some of them out until they can be caught off-guard. But unlike Leptons, Reptons can spread from bay to bay, so if you do not wipe out the Reptons in bay i, you may need to put in a force field to keep them from spreading to an unoccupied bay i+1.¹ All Reptons must be eliminated within m time units, or they will seize the entire space station for their own nefarious purposes.

Your task is to devise an algorithm that minimizes the cost of cleaning out the Reptons. Its output should be a cleaning schedule that specifies for each cargo bay i the time t_i at which it is cleaned, which may range from 1 to m. The cost is the sum of:

• A cleanup cost c_ij for each bay i that is cleaned at time t_i = j.

• A force-field cost s_ij for each bay i and time j, which is paid if t_i is greater than j but t_i+1 (or t₁ if i = n) is less than or equal to j.

Your algorithm should run in time polynomial in n and m.

1.1. Example (added 2004-04-11)

Suppose that bay 1 has costs

Suppose we clean out bay 2 at time 1.

If we clean out bay 1 at time 1, the total cost contributed by bay one is just c_{1 1} = 1.

If we clean out bay 1 at time 2, the total cost is s_{1 1} + c_{1 2} = 6.

If we clean out bay 1 at time 3, the total cost is s_{1 1} + s_{1 2} + c_{1 3} = 5.

If we do not clean out bay 2 before bay 1, we do not have to pay the containment costs.

2. A tripartite marriage problem

Realizing the worst fears of gay marriage opponents, the Commonwealth of Massachusetts not only votes down an anti-gay marriage amendment to its constitution but instead passes a competing amendment that states:

1. All marriages in the Commonwealth of Massachusetts shall consist of exactly three persons of age 18 or older.
2. No later than one year following the passage of this amendment, all persons of age 18 or older in the Commonwealth of Massachusetts who are not married shall be burned at the stake until dead.

The Massachusetts Supreme Judicial Court has asked you to determine if these two clauses are consistent with a much earlier amendment, passed in response to 17th-century Puritan excesses, that forbids both loveless marriages and burning at the stake. Specifically, they have compiled a list of all compatible triples (x,y,z) of Massachusetts adults that could conceivably be married, and wish to know the maximum number of Massachusetts adults that can be married off in such compatible triples, assuming no adult can be married in more than one triple.

Write an integer linear program that solves this problem (i.e. a linear program that solves this problem if you add the constraint that all variables must be integral). Give a counterexample for which the optimum without requiring integrality is fractional, or show that the linear program always has an integral optimum even without the integrality constraint.