2
$\begingroup$

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!

$\endgroup$
3
  • $\begingroup$ Excuse my density: what about putting vertex I in part J, where J = I mod k? I assume conseuctively numbered v ertices and parts. Gerhard "Ask Me About System Design" Paseman, 2011.05.19 $\endgroup$ May 19, 2011 at 20:27
  • $\begingroup$ But what about the case in which vertices are weighted? (Or general objects, not necessarily vertices, for the simplified version.) I am working with case where objects can have arbitrary weights. $\endgroup$
    – user15230
    May 19, 2011 at 21:53
  • $\begingroup$ I have edited my question to clarify that the objects/vertices can have arbitrary weights, thanks Gerhard. $\endgroup$
    – user15230
    May 19, 2011 at 22:00

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ Unfortunately I typically have several million arbitrarily weighted objects, sometimes much more, and am guessing this may qualify as huge. My guess is that heuristics that are tailored to the characteristics of this problem instead of the IP formulation may perform better. $\endgroup$
    – user15230
    May 20, 2011 at 0:06
  • $\begingroup$ I noticed the connection to Partition/3-Partition but they're not exactly instances of the problem I mention. Aren't partition/3-partition decision problems (vs the optimization problem in my question)? It's a relatively small difference I'll admit but... If possible, I'd really like to know if there is a name/proof for this k-partition optimization generalization of Partition/3-Partition. If no one can find a name/proof for the generalization after a few days, I'll assume neither exist and I'll mark your answer correct. :) (I've already googled for a few hours with no success.) $\endgroup$
    – user15230
    May 20, 2011 at 0:10
  • $\begingroup$ By definition, NP-completeness always refers to decision problems. A decision problem corresponding to your optimization problem would be: Given $n$ objects, an integer $k$ and a bound $L$, can they be partitioned in $k$ blocks such that the weights of two blocks differ by at most $L$. Partition: $k=2$, $L=0$ 3-partition: $k=m$, $L=0$ (the $m$ from the fromulation of 3-partition in my link) $\endgroup$ May 20, 2011 at 0:43
  • $\begingroup$ According to the abstract, the paper mysmu.edu/faculty/kyriakos/IJCAI11.pdf has a heuristic for minimizing the maximum weight difference, but subject to the additional constraint that the blocks contain roughly the same number of objects. $\endgroup$ May 20, 2011 at 1:32
  • 1
    $\begingroup$ I didn't find the Zhang et al paper you link to-- that's a good catch. Even though the paper requires an additional cardinality balance (not what I'm looking for), the paper itself cites other papers that are indeed about my problem (no cardinality constraint) and seem to hint there is no commonly agreed upon name, eg "set partitioning", "multiway number partitioning", etc. I knew such papers had to exist, but couldn't find them. Thanks! :) $\endgroup$
    – user15230
    May 21, 2011 at 7:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.