[EM] Breakthrough in political districting algorithms (I think)

[Warren Smith]

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