[EM] Advantages of Dirichlet Region Districts

[Ernest Prabhakar]

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.