Warren Smith wrote in part: > The "graph partitioning" problem is NP-complete:
I didn't express myself very well. Yes, the "graph-partitioning problem" is NP-complete, but my suggestion was that we didn't need the full power of that result. Instead we could reformulate the problem into a disection form (which as Adam Tarr has since pointed had already been suggested) and THAT class of problems is entirely P. Just remove the "minimize strength of broken connections" requirement and substitute "build up 'molecules' from the 'most connected' atoms that do not violate the population maximum criterion' and then accept ANY solution that cuts the entire state into N connected districts that all have about the same population." Techniques to do this in P-time are widely used (OK, I've used 'em to classify sports schedules. If they're not widely used it is not my fault). ---- Election-methods mailing list - see http://electorama.com/em for list info
