[EM] Advantages of Dirichlet Region Districts
Ernest Prabhakar
drernie at mac.com
Fri Jan 16 10:46:02 PST 2004
Alex & Matt,
I think these two questions are about the same:
Matt responds:
> the objectively measurable optimization goal (such as smallest total
> road cuts count or perimeters length) with objectively defined
> constraints (such as per district maximum acceptable population size
> deviance from ideal uniformity) defines a NP-complete or NP-hard
> problem and we cannot expect to find the ultimate solution due to
> large N then it is sensible to solicit proposals by declaring a
> competition (maybe offering the winner a cash award). Ties could be
> broken by selecting the proposal with the smallest maximum deviation
> district from population size uniformity and if still tied by the
> smallest second largest district deviation from district population
> size uniformity, etc.
On Jan 15, 2004, at 8:43 PM, Alex Small wrote:
> Finally, I do have one reservation about the Dirichlet method: In
> order
> to achieve (roughly) equal population, one must do a considerable
> amount
> of trial and error, adjusting district centers until the population
> variance is below some pre-determined criterion. Does anybody have
> thoughts about how to handle this problem tractably?
This is pretty much the same question. For problems that are not
directly computable but have objective criteria, it is straightforward
to use computational techniques to do a probabilistic search of the
parameter space to find a 'local minima' solution. True, none of these
is guaranteed to find the absolute global minima. On the other hand,
you can get extremely close in reasonable amount of time. You can also
run it in parallel on a SETI at Home type of environment very easily.
There's not risk of false data, since you have a public
objective-criteria.
I guess it is really a political question whether you decide one
implementation is 'good enough', or hold an open contest to see if
anyone can do better. The term 'contest' is perhaps what bothers me.
For us, I could imagine U.C. Berkeley (or some such) hosting the
'reference calculation', and inviting public comment by a certain date
to see if anyone can find a more optimal solution.
I've actually been working on a Python script to do such a calculation
this week, and its about half done, so I should have something fairly
good by the end of the month. It uses the criteria of:
a) minimum deviance
b) minimized (weighted) edges [which could be defined as road-traffic,
or anything else]
While it does not explicitly satisfy Dirlecht, I suspect most of the
districts generated by this criteria should come close.
If anyone wants to see the (in-process, not yet working, but
algorithmically interesting) code, let me know.
-- Ernie P.
More information about the Election-Methods
mailing list