Juho wrote:
The traditional algorithm complexity research covers usually only
finding perfect/optimal result. I'm particularly interested in how the
value of the result increases as a function of time. It is possible that
even if it would take 100 years to guarantee that one has found the best
The traditional algorithm complexity research covers usually only
finding perfect/optimal result. I'm particularly interested in how
the value of the result increases as a function of time. It is
possible that even if it would take 100 years to guarantee that one
has found the best
Juho wrote:
On Sep 4, 2008, at 0:59 , Kristofer Munsterhjelm wrote:
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
On Wed, Sep 3, 2008 at 1:57 PM, Brian Olson [EMAIL PROTECTED] wrote:
I checked my code and I'm not doing the expensive square root. It's not
quite the second though, it's actually:
((dx*dx + dy*dy) * weight)
The weight gets nudged by multiplying by 1.01 or 0.99. Squaring the weight
or not
Raph Frank wrote:
On Tue, Sep 2, 2008 at 11:00 PM, Kristofer Munsterhjelm
[EMAIL PROTECTED] wrote:
The reasonable thing to use would be Euclidean distance, since that makes
sense, given the geometric nature of the districting problem. If you want to
be even more accurate, you can use great
I haven't been following this thread in great detail, but I do have a
question: what is the distance function actually trying to measure and
minimize? What exactly are we trying to optimize when we minimize
distance, by whatever measure? I might be close in a crow's-flight
sense to a
On Wed, Sep 3, 2008 at 8:35 PM, Kristofer Munsterhjelm
[EMAIL PROTECTED] wrote:
If you use a Mercator projected map, you're just hiding the quantization.
All maps have some distortion, and since the map projection uses
trigonometric functions, you can just use the Haversine distance directly.
On Wed, Sep 3, 2008 at 8:46 PM, Jonathan Lundell [EMAIL PROTECTED] wrote:
OK, we could solve that in principle (though not too quickly) by using
Google Maps driving time, or the like. But what does driving time have to do
with grouping voters (unless we're drawing a precinct and measuring
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
On Sep 1, 2008, at 7:28 AM, Kristofer Munsterhjelm wrote:
A simpler algorithm, though one that doesn't give any worst-case
bounds, is Lloyd's algorithm. Start with random center points, then
calculate the centroids for the current Voronoi cells. Move the
center points towards the centroid
On 9/2/08, Brian Olson [EMAIL PROTECTED] wrote:
I have implemented essentially that, and it pretty quickly gets pretty good
results as measured by the distance per person to land-area-center test. I
added one thing to deal with variations in population density. Each district
center also has
On Sep 2, 2008, at 6:00 PM, Kristofer Munsterhjelm wrote:
Your reference to a Cd variable to get population proportionality is
interesting. I think part of the problem that you're trying to fix
here comes from that clustering (such as by Lloyd's algorithm)
optimizes for energy instead of
On 9/1/08, Michael Rouse [EMAIL PROTECTED] wrote:
There was a discussion of district-drawing algorithms on the
election-methods list a few years back. I've always thought that taking
centroidal Voronoi cells with equal populations was an elegant way to do it.
Here's an example of standard
Michael Rouse wrote:
There was a discussion of district-drawing algorithms on the
election-methods list a few years back. I've always thought that taking
centroidal Voronoi cells with equal populations was an elegant way to do
it. Here's an example of standard Voronoi cells and the
On 9/1/08, Kristofer Munsterhjelm [EMAIL PROTECTED] wrote:
Those maps could be pruned so that only the Pareto front remains. That is,
if there's some map that's worse on all metrics with regards to some other
map, then that first map isn't included. As long as there are enough metrics
to give
From: Kathy Dopp [EMAIL PROTECTED]
From: Raph Frank [EMAIL PROTECTED]
Brian Olson suggests this approach for his anti-gerrymandering proposals.
http://bolson.org/dist/USIRA.html
and
http://bolson.org/dist/
I suggested a similar mathematical method for drawing Congressional
districts a few
There was a discussion of district-drawing algorithms on the
election-methods list a few years back. I've always thought that taking
centroidal Voronoi cells with equal populations was an elegant way to do
it. Here's an example of standard Voronoi cells and the centroidal
version I pulled
17 matches
Mail list logo
