[Oops.] Subtle omission in Lemma 4.1 and 4.2

[jeffgerickson]

Reported by Neal Young via email:

I'm wondering about a possible error in your book's Chapter 4 on greedy algorithms. Specifically, in Lemmas 4.1 and 4.2 in Section 4.1 [1]. The statement of Lemma 4.1 is

Lemma 4.1 E[cost(\pi)] is minimized when L[\pi(i)] \le L[\pi(i + 1)] for all i.

Equivalently (as I interpret it, at least)

If L[\pi(i)] \le L[\pi(i + 1)] for all i, then E[cost(\pi)] is minimized.

But what the proof shows is the converse:

if L[\pi(i)] > L[\pi(i + 1)] for some i, then E[cost(\pi)] is not minimized.

That is,

if E[cost(\pi)] is minimized, then L[\pi(i)] \le L[\pi(i + 1)] for all i.

I think some additional argument is needed to get from this (what is proved) to the actual statement of Lemma 4.1, especially when the lengths L are not distinct. Something like: Let pi be a permutation of minimum cost. By the given proof, it orders the files by non-decreasing length. And any permutation pi that does that (which might not be pi) has the same cost, so must also be optimal.

The gap also appears in the proof of Lemma 4.2, but there it is worse, as the ratio of length to weight for two files can be the same even when their lengths are not the same and their weights are not the same. So closing the gap requires a more sophisticated argument.

Of course having to explicitly deal with this technicality is ugly, so perhaps you've deliberately glossed over it for the sake of readability? I would have reservations about doing that, as it's a technical detail whose omission leaves a gap that can hide a conceptual error that students often make.

[jeffgerickson]

Neal is correct; I was implicitly assuming distinct lengths and distinct length/weight ratios. The proof is still correct without that assumption, but incomplete.

Change "when" to "if and only if" and add a few sentences to each proof observing that every permutation that sorts the lengths or ratios leads to the same cost, and so all such permutations are optimal.