[EM] A computationally feasible method (algorithmic redistricting)

[Juho]

On Sep 4, 2008, at 0:59 , Kristofer Munsterhjelm wrote:

> Brian Olson wrote:
>> I guess my time in Computer Science land has left me pretty  
>> comfortable with the idea that there are lots of problems that are  
>> too hard to ever reliably get "the best solution". I don't know if  
>> there's a short-short popularizing explanation of how finding a  
>> good solution is Hard while measuring the quality of a solution is  
>> pretty quick.
>> If anybody asks and it's not the time, place, or audience for  
>> discussing NP Hard problems, I will wave my hands and say, "Hey,  
>> look over there! Good results, on my one puny computer! With more  
>> it'd only get better!"
>
> I think puzzles and games make good examples of NP-hard problems.  
> Sokoban is PSPACE-complete, and it's not that difficult to show  
> people that there are puzzles (like ciphers) where you know if a  
> solution is right, but it takes effort to find the solution. That's  
> pretty much the point of a puzzle, after all (although not all  
> puzzles are NP-hard; they can be fun even if they're not, as long  
> as they do something for which it's challenging to find a solution).

Puzzles and ciphers are good examples of cases where general  
optimization may typically fail to find even a decent answer (well,  
in these example cases the solution must be 100% good or it is no  
good at all). My assumption was that in the area of voting methods it  
would be typical that general optimization methods are sufficient and  
will with good probability lead to good enough results. Are there and  
counterexamples to this?

Juho





		
___________________________________________________________ 
The all-new Yahoo! Mail goes wherever you go - free your email address from your Internet provider. http://uk.docs.yahoo.com/nowyoucan.html