http://rangevoting.org/SpaceFillCurve.html
describes a new, incredibly simple, algorithm for political districting which is guaranteed to get within a constant factor (namely 6.34) of the cost of the optimum districting, using the cost measure sum(over all people) (distance to their district centerpoint)^2. Its output can be fed into further optimizers... but my point is that no previous polynomial-time algorithm had ever been able to guarantee being at most any constant factor worse than optimal. I hope this paper is not insane -- it seems almost too good+simple to be true. Email me your questions, comments, complaints, etc about the paper. (I am also working on a much more complicated polytime algorithm which if it pans out will be able to guarantee 1+epsilon approximation...) -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step) and math.temple.edu/~wds/homepage/works.html ---- Election-Methods mailing list - see http://electorama.com/em for list info
