most recent 30 from http://mathoverflow.net 2013-05-23T05:31:01Z http://mathoverflow.net/feeds/question/65472 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/65472/official-name-and-complexity-of-k-way-balanced-set-partitioning-what-is-the-bes artif 2011-05-19T20:14:42Z 2011-05-20T09:46:26Z

<p>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 <a href="http://en.wikipedia.org/wiki/Graph_partitioning" rel="nofollow">http://en.wikipedia.org/wiki/Graph_partitioning</a>). </p> <p>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?</p> <p>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. </p> <p>Is there a real name for this problem (other than the one I made up in the title)? </p> <p>And does anyone know of a formal paper or some other official, citable source proving its complexity?</p> <p>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?</p> <p>(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?)</p> <p>Thanks!</p>

http://mathoverflow.net/questions/65472/official-name-and-complexity-of-k-way-balanced-set-partitioning-what-is-the-bes/65485#65485 Thomas Kalinowski 2011-05-19T23:13:28Z 2011-05-20T09:46:26Z

<p>The problem is NP-complete, because it contains the problems Partition and 3-Partition (problems 41 and 46 in <a href="http://www.csc.liv.ac.uk/~ped/teachadmin/COMP202/annotated_np.html" rel="nofollow">http://www.csc.liv.ac.uk/~ped/teachadmin/COMP202/annotated_np.html</a>). 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).</p> <p>For a heuristic, local search seems to be a natural approach. After greedily generating a start solution you can repeat the following steps.</p> <ul> <li>pick blocks $A$ and $B$ with maximal weight difference $w(A)-w(B)$</li> <li>find subsets $A'\subseteq A$ and $B'\subseteq B$ such that <code>$|w((A\setminus A')\cup B')-w((B\setminus B')\cup A')|&lt;w(A)-w(B)$</code></li> <li>replace $A$ by <code>$(A\setminus A')\cup B'$</code> and $B$ by <code>$(B\setminus B')\cup A'$</code></li> </ul> <p>To spice it up a bit one could GRASP it (see <a href="http://en.wikipedia.org/wiki/Greedy_randomized_adaptive_search_procedure" rel="nofollow">http://en.wikipedia.org/wiki/Greedy_randomized_adaptive_search_procedure</a> ). 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. </p>