[EM] A practical matter for Ranked-Pairs, among other methods
Eric Gorr
ericgorr at cox.net
Tue Jan 14 13:27:57 PST 2003
(I'll return to the odd RP case I just presented soon)
Several methods for determining the winner are based on algorithms
which for a large enough N (where N is the number of options to be
ranked) could take longer to compute then the amount of time the
Universe has been in existence...that N is probably not very much
different then the N that would take an average human lifetime to
complete.
For example, the computation on which Ranked-Pairs or Beatpath Winner
is based, in large part, on Floyd's Algorithm, which runs in O(N^3)
time.
I was just wondering if anyone had researched this very real problem
of just how large N could become before it became impractical to use
for a particular election.
----
For more information about this list (subscribe, unsubscribe, FAQ, etc),
please see http://www.eskimo.com/~robla/em
More information about the Election-Methods
mailing list