Problem of the Week (bin-packing variation)

Here's introducing another intended use of this blog. I will try to periodically post a problem, probably computer science or math related, that I find interesting. It'll typically have to do with my work, or possibly the work of someone else I know. Please feel free to discuss, talk about similar problems, etc. I'm posting because I think the problems are interesting, not because I'm trying to milk ya'll for solutions (well, at least not this time). In addition, if I didn't describe the problem sufficiently, say so! One of the founding principles of this blog is that I need to work on my communication skills (or "skizzillz," if you will).

The Problem:

This is a variation of the bin-packing problem. I have N objects, each with a weight. I want to completely divide these objects into M bins in such a way that the total weight of the heaviest bin is minimized. (Well, I guess it's not really a variation yet, keep reading)

More Details:

In the actual example of this I'm working with, I don't actually need the best solution. All I care about is that I get a solution that's "close" to optimal. If the maximal weight of the optimal solution is W, I only need a solution whose maximal weight is a * W (I'd say "a" is somewhere between 1.1 and 1.5). Furthermore, I need to find this "reasonable" solution in less than N^2 time.

As to the typical values of N and M, N is typically at least on the order of thousands, and could potentially be in the millions. M will typically be in the tens to hundreds, but could potentially go as high as the low thousands.

The actual weights of the objects aren't completely random, either. There are actually a very small number of discrete weights, on the order of ten or so, and these discrete weights differ by at most a factor of ten in value. They are all positive. In addition, though the actual weights are taken from a small number of possible values, they are sampled inaccurately, and could have relatively small variations--this could be disregarded, but adds additional complexity should you wish to group the objects by discrete weight.

A (Likely) Sufficient Solution

The following is probably sufficient, and runs in O(N log N) time.

First, sort your list of object weights.
O(N log N)

Now, compute the total weight, and call this Wtotal.
O(N)

Next, compute a "target" weight using the following formula:
Wtarget = a * Wtotal / N
O(1)

Now, for each bin, take this "greedy" approach:
Take objects from the "heavy" end of the list until we can't take any more without going over the target. Then do the same from the "light" end.
O(N)

Finally, there will probably be some objects left over, iterate over them (starting from the heavy end) and dish them out to the currently-lightest bin.
O(log N) (typically--I might be wrong on this, sort of just guessing)
O(N log N) (pathological cases)
O(log M) (There's another sub-linear N term missing from here, not dominant overall though)
O(N log M) (pathological cases)

It's sloppy and probably easily improved upon, but it suits my needs (I think). Please feel free to mention something cooler/better/sexier/etc!