most recent 30 from http://mathoverflow.net 2013-05-19T06:37:18Z http://mathoverflow.net/feeds/user/15230 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 2011-05-21T07:12:54Z 2011-05-21T07:12:54Z

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 &quot;set partitioning&quot;, &quot;multiway number partitioning&quot;, etc. I knew such papers had to exist, but couldn't find them. Thanks! :)

http://mathoverflow.net/questions/65472/official-name-and-complexity-of-k-way-balanced-set-partitioning-what-is-the-bes/65485#65485 2011-05-21T07:09:56Z 2011-05-21T07:09:56Z

Yeah you're totally right about only decision problems being technically NP-Complete. I forgot about that somehow. Looking at your formulation, it seems you're right that Partition/3-Partition are totally subsumed by the decision version of my problem, so I guess maybe no one has made a specific attempt to prove it is NP-Complete since it's too obvious.

http://mathoverflow.net/questions/65472/official-name-and-complexity-of-k-way-balanced-set-partitioning-what-is-the-bes/65485#65485 2011-05-20T00:10:45Z 2011-05-20T00:10:45Z

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.)

http://mathoverflow.net/questions/65472/official-name-and-complexity-of-k-way-balanced-set-partitioning-what-is-the-bes/65485#65485 2011-05-20T00:06:39Z 2011-05-20T00:06:39Z

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.

http://mathoverflow.net/questions/65472/official-name-and-complexity-of-k-way-balanced-set-partitioning-what-is-the-bes 2011-05-19T22:00:51Z 2011-05-19T22:00:51Z

I have edited my question to clarify that the objects/vertices can have arbitrary weights, thanks Gerhard.

http://mathoverflow.net/questions/65472/official-name-and-complexity-of-k-way-balanced-set-partitioning-what-is-the-bes 2011-05-19T21:53:38Z 2011-05-19T21:53:38Z

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.