[EM] Impractical districting idea, complexity

[Kristofer Munsterhjelm]

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 four-district 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 flood-fills 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 banana-shaped. 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