As you said: the Knuth/Plass algorithmn does not reduce or even detect rivers. Detecting rivers can be done in linear time, but reducing is very likely to put the algorithm in a higher time complexity class (which is almost linear with input length for the normal algorithm!).
Rivers are killed naturally except for pathological edge cases when you (a) do proper hyphenation, and (b) do something like the TeX algorithm for paragraph layout, and (c) adjust inter-letter space as well as inter-word space.
http://en.wikipedia.org/wiki/River_(typography)
edit: re-reading this seems to follow naturally from reducing the size of the gaps between words, which the algorithm does.