Official name and complexity of k-way balanced set partitioning?  What is the best heuristic? 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!
 A: The problem is NP-complete, because it contains the problems Partition and 3-Partition (problems 41 and 46 in http://www.csc.liv.ac.uk/~ped/teachadmin/COMP202/annotated_np.html). If your instances are not extremely huge, I would give an integer programming formulation a try. The heuristics build into modern solvers will probably be competitive (and come without any implementation work on your side).
For a heuristic, local search seems to be a natural approach. After greedily generating a start solution you can repeat the following steps.


*

*pick blocks $A$ and $B$ with maximal weight difference $w(A)-w(B)$

*find subsets $A'\subseteq A$ and $B'\subseteq B$ such that $|w((A\setminus A')\cup B')-w((B\setminus B')\cup A')|<w(A)-w(B)$

*replace $A$ by $(A\setminus A')\cup B'$ and $B$ by $(B\setminus B')\cup A'$


To spice it up a bit one could GRASP it (see http://en.wikipedia.org/wiki/Greedy_randomized_adaptive_search_procedure ). That just means that the greedy generation of the start solution is randomized: instead of adding the heaviest object to the lightest block, an object, randomly chosen from the $k_1$ heaviest is added to a block randomly chosen from the $k_2$ lightest. Then you start the local search, and when that becomes boring, you just generate a new randomized greedy start solution. This procedure is iterated very often with varying $(k_1,k_2)$, and one can keep track of which parameters $(k_1,k_2)$ tend to lead to good solutions.    
