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.