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!



Official name and complexity of k-way balanced set partitioning?  What is the best heuristic?
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. 


