The chairman assignment problem is stated thus: “Suppose k states form a union and every year a union chairman has to be selected in such a way that at any time the accumulated number of chairmen from each state is proportional to its weight” [1]. The carpool problem is that of choosing whose turn it is to drive. In both cases, we must allow for the fact that not everyone participates in every instance. These intuitive descriptions are unfortunately missing from this paper.

The title of the paper is somewhat misleading. The paper proves that the greedy algorithm is optimal among online (that is, where we have to decide what to do without knowing what the future will bring) algorithms--not that the online greedy algorithm is optimal. In fact, for the chairman problem, the authors admit that off-line algorithms (ones that can process the whole input, rather than having to make decisions on the fly) can have better behavior.

Let E_i(t) be the error for the ith participant at time t--that is, the amount by which the ith participant has overperformed or underperformed (since two people can’t share a chair or a driving duty, we can’t have fractions, so inequality is often necessary). This paper considers optimality in the sup-norm for E(t)--that is, wanting the biggest error to be as small as possible rather than, say, minimizing the average error. In reality, a small state whose quota is 0.7 but has never chaired might feel more aggrieved than a large state whose quota is 52 and has chaired 51.1 times.

This review is not to detract from the technical importance of the paper, but rather to encourage more research with other norms.