[EM] solving the NP-hard problem? no. The CRV approach to gerrymandering.

[Abd ul-Rahman Lomax]

At 05:52 PM 8/21/2005, Warren Smith wrote:
>I believe the brute force approach of just solving the NP-hard 
>redistricting problem
>perfectly, is not feasible.  There are probably ten-thousands of census blocks
>and exponential runtimes with that much input just do not happen, even with
>all the computer power on the planet on your side.

And suddenly a light bulb goes off. Census blocks. How are they defined?

Requiring district boundaries to follow census block boundaries could 
simplify the problem.

>Occasionally it is possible to reduce the growth constant in the exponential
>to incredibly small values, but I doubt that is the case here, and even
>if it were, then we could not be sure it would always work after the census
>data changed next time.

I'll agree that finding the maximized solution is probably impossible, but 
that is an unnecessary goal. There have been two possible solutions 
suggested: first, as long as there is an objective measure of how closely a 
proposed solution gets to the idea, it becomes possible to compare 
solutions. And then a deadline could be set: submit a proposed solution by 
a certain deadline. The best solution submitted by that deadline, as 
measured by the criterion, is adopted.

The other possible solution is to use an algorithm that does not produce 
the optimum result, but that would produce a result within a certain 
distance from optimum. The recursive district growth algorithm I proposed 
would be an example, assuming it works. A better algorithm might certainly 
be found.

The difficulty, really, is in defining the measure of success, for the 
first approach. For the second approach, simple location data for 
registered voters would be used for the simplest algorithm. Note that 
districts are based on population, not on the number of registered voters. 
Using census districts might get around this; alternatively, voters might 
be "weighted" by a ratio based on census district of residence, so that 
population ends up equal in each district.

>Also, even if exact solve were possible, then there would be a lot of 
>subjective
>input about "transportation lanes" etc.

There are legal definitions for roads of various kinds. I'd simply assign a 
speed to roads of various classes, possibly adjusted for areas of high 
population density. It would not have to be perfect. It simply needs to be 
clear and produce calculated travel times that are not drastically at odds 
with the reality.

I'd neglect extraordinary transportation other than regularly scheduled 
service where ordinary roads don't serve an area. (Such as islands; if 
there is no regularly scheduled ferry, the population is probably very low 
and it won't matter a great deal where an island is assigned. How about 
letting such areas vote on the issue? -- population below a certain 
threshhold, an area can, perhaps by two-thirds vote of residents, change 
its district....