[EM] An impractical suggestion for redistricting

[Kristofer Munsterhjelm]

I was reading https://arxiv.org/pdf/1901.04628.pdf, which gives an
approximation to hard capacitated k-means clustering (basically,
districting with the constraint that each district population should be
the same).

On page 4 the authors give a linear program that finds the optimally
compact capacitated clustering by Euclidean distance if the district
centers are given.

So this suggests the following algorithm: let the legislature (or the
public through a contest) choose k such centers. Solve the linear
program where each point is a person, and then use the assignments to
draw the districts.

The idea is that the degrees of freedom, the knobs that the legislature
can tweak, are limited to such a degree that gerrymandering becomes very
difficult. For instance, there probably does not exist *any* centroid
assignment that would reproduce the infamous Illinois earmuff district.


In practice, this is kind of useless because:
	- while strictly speaking polytime, the linear program has O(kn)
variables (k being the number of districts, n the state population), so
the linear program will be very large for large states,
	- US redistricting is limited to whole zip code regions (if I recall
correctly), while this program would cut across them. Perhaps replacing
individual points with weighted points representing one region each
would both solve this and the previous problem, but I'm not sure that
the resulting problem would be totally unimodular any longer,
	- the legislators probably wouldn't accept it (turkeys don't vote for
Christmas),
	- even if it were implemented, minor parties would still be cracked due
to their diffuse support. PR is the better choice.

But as a mathematical observation, it's pretty neat!

-km