>1. Rank processes by "badness" and kill the baddest one. This is not just based on memory usage, but is a fairly complicated and expensive algorithm.

AFAIK the algorithm has been simplified greatly: it's now just amount of memory weighted by the oom_score which can be set from userspace.