Here is my attempt at an algorithm for calculating the best beat
path values, as used in methods such as Schulze.
I am assuming this is still an open question.
Start with a matrix M[n][n] This matrix should either have the
margins of victory, or the number of votes on the winning side,
depending on your point of view. Both should have MAXVALUE along
the i=j diagonal.
I have presented it as a C code fragment.
dirty=1;
while(dirty) { /* check if change made */
dirty=0;
for(i=0;i<n;i++) { /* each row */
for(j=0;j<n;j++) { /* each column */
for(k=0;k<n;k++) { /* column in corresponding
candidate's row */
int s=min(M[i][j],M[j][k]);
/* combined path has the
minimum strength of its
components */
if(s>M[i][k]) { /* found a better path */
M[i][k]=s;
dirty=1;
}
}
}
}
}
The idea is simply to find obvious beat-path improvements until
M holds the best beat paths.
This is a polynomial-time algorithm since
1. The for loops all have polynomial bounds
2. The while loop can only continue as changes are made
There are only n^2 cells, and they can only be changed to greater
values existing in the matrix. Since there can only be n^2 such
values, n^4 is an obvious upper bound for the while loop.
So, the whole thing is polynomial-time.
-----== Sent via Deja News, The Discussion Network ==-----
http://www.dejanews.com/ Easy access to 50,000+ discussion forums
