[EM] Impractical districting idea, complexity

[Forest Simmons]

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?

El jue., 9 de jun. de 2022 2:41 p. m., Kristofer Munsterhjelm <
km_elmet at t-online.de> escribió:

> A private post by Forest Simmons made me realize that finding the proper
> boundaries for districts given their centers is the same problem as
> finding the assignment of voters to candidates in Monroe's method for a
> particular winning assembly.
>
> Monroe (the cardinal version) works like this: Each voter rates each
> candidate. The quality of some given winning assembly is the sum of
> ratings that each voter gives to his assigned winning candidate, under
> the following constraints:
>         - each candidate must be assigned the same number of voters
>         - this rating sum should be as high as possible.
>
> So we can imagine a bipartite graph with all the voters on the left, the
> winning candidates on the right, and we want to pick one edge from each
> voter to one of the candidate to maximize the sum of the edge weights
> (the ratings), under the constraints given.
>
> But the districting problem is just the same, except we're minimizing
> instead of maximizing: let the "rating" of voter x for "winner" y be the
> squared distance from person x to center y. We want to assign people to
> districts so that the sum of squared distances is minimized, under the
> constraint that each district must have the same number of inhabitants.
>
> Since minimization and maximization is equally hard, that means that all
> the algorithm results Warren give on
> https://rangevoting.org/MonroeMW.html apply to the districting problem.
>
> (Furthermore, the construction doesn't need the metric to obey any sort
> of nice property. So if you'd like to make the distance from point x to
> y some estimate of the time it would take to walk from x to y, then you
> can get naturally-shaped districts... if so desired. Maybe not so
> practical for political redistricting, but perhaps if you want to draw
> county maps for a fictional country?)
>
> The reduction is better than using linear programming... but it doesn't
> help.
>
> If there are k districts and the state population is p, then there are
> (p+k) nodes in the graph and m=p*k edges. The complexity of the
> assignment algorithm is just about O(p^2k + p^2 log p). The p^2 is the
> killer. Suppose we have a population of a million, then p^2 = 1e12. Ouch.
>
> Other stuff/ideas:
>         https://www.bowaggoner.com/courses/2019/csci5454/docs/approx.pdf
> gives
> the approximation factor for *maximum* matching with the simple greedy
> algorithm of always admitting the person who's closest to some center,
> to that center, until everybody's assigned. (But this doesn't have
> capacity constraints? I'm not sure?)
>         https://people.cs.vt.edu/~sharathr/as_match.pdf gives approximate
> matching with metric costs, but there's still an n^2 (i.e. p^2) term to
> its complexity.
>         Sampling would seem to be the obvious solution (just look at 1000
> people or so), but as I understand it, the population constraints on
> districting are exact: districts are not allowed to have even the
> smallest difference in populations, which excludes approaches based on
> randomness.
>
> -km
> ----
> Election-Methods mailing list - see https://electorama.com/em for list
> info
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.electorama.com/pipermail/election-methods-electorama.com/attachments/20220609/01f8875e/attachment.html>