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 solution
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 takes
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
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 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 t
Jonathan Lundell wrote:
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-fl
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 directl
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 neig
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 cir
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
Kristofer Munsterhjelm wrote:
> On the other hand, approximating may make strategy more difficult. I
> think Rob LeGrand wrote something about how approximations to minimax
> Approval obscured the strategy that would otherwise work.
Yes, you're thinking of
http://www.cse.wustl.edu/~legrand/legran
On Sep 3, 2008, at 5:32 AM, Raph Frank wrote:
On 9/3/08, Brian Olson <[EMAIL PROTECTED]> wrote:
Anyway, what my pseudo-voronoi solver does is this:
Initialization:
• Assign district centers to random points (block
coordinates).
• Assign census blocks to nearest district cent
On 9/3/08, Brian Olson <[EMAIL PROTECTED]> wrote:
> I'm looking at fryer.pdf and maybe the notation is a little thick for me
> but it looks like the pi(V_s) equation number 1 in section 3.2 is summing,
> for each district, the distance between every voter in the district and
> every other voter in
On Sep 2, 2008, at 0:58 , Kristofer Munsterhjelm wrote:
Juho wrote:
Here's one practical and simple approach to guaranteeing
computational feasibility of some otherwise complex election methods.
The original method might be based e.g. on evaluating all possible
sets of n candidates and then ele
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 ma
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 circle distance in
Raph Frank wrote:
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 distri
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 als
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, Kristofer Munsterhjelm <[EMAIL PROTECTED]> wrote:
> This can't be exhaustive, since the ordering alone requires lg((n choose
> k)!) bits, and the full Condorcet matrix is (n choose k)^2. But maybe it'll
> be good enough?
Should be OK.
The process could have multiple rounds. After the
Raph Frank wrote:
On Mon, Sep 1, 2008 at 10:58 PM, Kristofer Munsterhjelm
<[EMAIL PROTECTED]> wrote:
In multiwinner election situations (like CPO-STV), the randomness might make
the losers complain that they lost because the assembly that the
optimization algorithm stumbled on didn't include the
On Mon, Sep 1, 2008 at 10:58 PM, Kristofer Munsterhjelm
<[EMAIL PROTECTED]> wrote:
> In multiwinner election situations (like CPO-STV), the randomness might make
> the losers complain that they lost because the assembly that the
> optimization algorithm stumbled on didn't include them, not because
Juho wrote:
Here's one practical and simple approach to guaranteeing
computational feasibility of some otherwise complex election methods.
The original method might be based e.g. on evaluating all possible
sets of n candidates and then electing the best set. Comparing all
the sets is usually not
Juho wrote:
Here's one practical and simple approach to guaranteeing
computational feasibility of some otherwise complex election methods.
The original method might be based e.g. on evaluating all possible
sets of n candidates and then electing the best set. Comparing all
the sets is usually not
uricius, Vermont USA
- Original Message -
From: "Kristofer Munsterhjelm" <[EMAIL PROTECTED]>
To: "Michael Rouse" <[EMAIL PROTECTED]>
Cc:
Sent: Monday, September 01, 2008 7:28 AM
Subject: Re: [EM] A computationally feasible method
(algorithmicredistricting)
M
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
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 centroidal
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 stand
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 off
> 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 Congressi
> Date: Sun, 31 Aug 2008 13:25:49 +0100
> From: "Raph Frank" <[EMAIL PROTECTED]>
> Subject: Re: [EM] A computationally feasible method
> Brian Olson suggests this approach for his anti-gerrymandering proposals.
>
> http://bolson.org/dist/USIRA.html
> and
>
On Aug 31, 2008, at 15:25 , Raph Frank wrote:
On Sat, Aug 30, 2008 at 5:46 PM, Juho <[EMAIL PROTECTED]> wrote:
To gain even
better trust that this set is the best one one could publish the
best found
set and then wait for a week and allow other interested parties to
seek for
even better se
On Sun, Aug 31, 2008 at 4:29 PM, Brian Olson <[EMAIL PROTECTED]> wrote:
>
> On Aug 31, 2008, at 8:25 AM, Raph Frank wrote:
>> Ofc, he doesn't define "geographic centers of the districts", which
>> presumably means the centre of gravity of the district.
>
> I'm pretty sure I want the average point o
On Aug 31, 2008, at 8:25 AM, Raph Frank wrote:
On Sat, Aug 30, 2008 at 5:46 PM, Juho <[EMAIL PROTECTED]> wrote:
To gain even
better trust that this set is the best one one could publish the
best found
set and then wait for a week and allow other interested parties to
seek for
even better
On Sat, Aug 30, 2008 at 5:46 PM, Juho <[EMAIL PROTECTED]> wrote:
> To gain even
> better trust that this set is the best one one could publish the best found
> set and then wait for a week and allow other interested parties to seek for
> even better sets. Maybe different parties or candidates try t
Here's one practical and simple approach to guaranteeing
computational feasibility of some otherwise complex election methods.
The original method might be based e.g. on evaluating all possible
sets of n candidates and then electing the best set. Comparing all
the sets is usually not comput
37 matches
Mail list logo
