(Incidentally, this problem—producing the ideal packing into fixed-sized pages of a set of arbitrarily-sized objects—is NP-complete, and therefore likely impossible to solve optimally in polynomial—i.e., reasonable—time.)
Aren't there polytime algorithms that approximate to a certain percentage of the optimum?
yes[0], the author mentions "first fit" which presumably is "first fit decreasing" which is one of those.
His approach was, from what I understand, to try a few approximate techniques and choose the best result without trying to run an exact algorithm with unbounded time.
Yes, but approximate algorithms for NP-hard problems hadn't been as thoroughly studied back then -- this was 1996, after all -- and even if I'd had the appropriate papers at hand, I probably wouldn't have invested the effort to implement anything complicated. There was just simply too much to do in too little time. The simple approximation using greedy packing did pretty well in practice; I'm sure how close that comes to optimal is well understood by now.
Aren't there polytime algorithms that approximate to a certain percentage of the optimum?