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....
----
Election-methods mailing list - see http://electorama.com/em for list info
