4 added 9 characters in body

As a lot of people know, graph partitioning is NP-Complete. In graph partitioning, you try to create k balanced (within some pre-specified epsilon) disjoint subsets of (possibly weighted) vertices such that the edgecut is minimized. (See http://en.wikipedia.org/wiki/Graph_partitioning).

But what about the simpler problem of partitioning a set of arbitrarily weighted objects into k balanced disjoint subsets, seeking to minimize not some edgecut (only applicable to graph) but the imbalance itself?

It seems this simpler problem is itself still either NP-Complete or at least NP-Hard, based on similarity to problems such as Graph Partitioning, Bin Packing, Subset Sum, Multiprocessor Scheduling, Set Cover, etc.

Is there a real name for this problem (other than the one I made up in the title)?

And does anyone know of a formal paper or some other official, citable source proving its complexity?

Last but not least, and this is the primary reason why I am looking for the name/complexity, what is the best known heuristic for this problem?

(I am currently doing a greedy approach-- iteratively placing the next heaviest object in the total set on the currently lightest partition. But is it possible to do better?)

Thanks!

2 weights!

As a lot of people know, graph partitioning is NP-Complete. In graph partitioning, you try to create k balanced (within some pre-specified epsilon) disjoint subsets of (possibly weighted) vertices such that the edgecut is minimized. (See http://en.wikipedia.org/wiki/Graph_partitioning).

But what about the simpler problem of partitioning a set of arbitrarily weighted objects into k balanced disjoint subsets, seeking to minimize not some edgecut (only applicable to graph) but the imbalance itself?

It seems this simpler problem is itself still either NP-Complete or at least NP-Hard, based on similarity to problems such as Graph Partitioning, Bin Packing, Subset Sum, Multiprocessor Scheduling, Set Cover, etc.

Is there a real name for this problem (other than the one I made up in the title)?

And does anyone know of a formal paper or some other official, citable source proving its complexity?

Last but not least, and this is the primary reason why I am looking for the name/complexity, what is the best known heuristic for this problem?

(I am currently doing a greedy approach-- iteratively placing the next object in the total set on the currently lightest partition. But is it possible to do better?)

Thanks!

1