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