[EM] Impractical districting idea, complexity
Kristofer Munsterhjelm
km_elmet at tonline.de
Fri Jun 10 02:51:08 PDT 2022
On 6/10/22 12:58 AM, Forest Simmons wrote:
> Kristofer,
>
> In your original "impractical" suggestion, you had a contest to see who
> could come up with the best set of district centers. At worst you would
> have a few thousand of these to check.
>
> Wouldn't some polytime greedy algorithm make this practical?
The complexity I gave is for the algorithm that, given center locations,
provides the optimal districting with these given centers. So every time
someone proposes say, four district centers for a fourdistrict state,
the system has to do O(p^2 * 4 + p^2 log p) operations to draw the
actual districts and figure out how good the proposal is.
Finding optimal *centers* is harder still.
The most manageable approach would seem to be to find some kind of
approximation to the "given centers, find districts" problem. But it has
to be good enough to preserve desirable properties (e.g. districts not
being disconnected).
The obvious greedy variant is to just sort all the edges by distance
(takes O(pk log pk) time, or p log p if the k is vanishingly small
compared to p), and then go down the list, admitting (center, person)
pairs until the given center is full (which takes O(pk) time). But this
is kinda just a flood fill and could result in failure in pathological
situations  e.g. a linear state with three centers next to each other,
like this
=================+

A B C 
=================+
where B floodfills fast enough to cut C off from A, thus making it
impossible to preserve the population constraint. (The optimal solution
would have a very thin sliver going from B in the direction of A, so
that C would be kind of triangular or bananashaped. This would indicate
that it's a pretty poor choice of centers.)
There may exist better approximations that are not too slow, but I
couldn't find any and I had to go, so I just tossed some links at the
end of my post :)
If I'm to investigate the problem further, I also have to find out how
Warren can impose capacity constraints and still use just the ordinary
assignment algorithm. As shown above, the greedy algorithm doesn't
preserve the capacity constraints, but it would (I think) approximately
solve the assignment problem... so perhaps a transformation of the
problem is needed before passing it to the assignment algorithm.
km
More information about the ElectionMethods
mailing list