[EM] Schulze STV question

[Brian Olson]

49 seconds to count 366 votes is pretty rough. Even if all the explosive
combinatorics is in Candidates and Seats and that just scales linearly with
additional votes, anything more than a small town starts to take all day to
compute.

On Sun, Jan 15, 2017 at 7:21 AM, Markus Schulze <
markus.schulze at alumni.tu-berlin.de> wrote:

> Hallo,
>
> when there are S seats and C candidates (with C > S),
> then there are C!/(S!*(C-S)!) possible ways to fill
> these seats. When you compare every possible way
> to fill these seats with every other possible way
> that differs in exactly one candidate, then you have
> to make C!/(S!*(C-S-1)!) comparisons. This cannot be
> done in a runtime that is polynomial in S and C.
>
> The largest example in Tideman's database is example A90
> with S=12 seats and C=20 candidates. It takes 49.0 s
> (on a computer with two 6-core "E5-2630v2 @ 2.60 GHz"
> processors) to calculate the winning set of Schulze STV.
> See section 10.3 of this paper:
>
> http://m-schulze.9mail.de/verylong.pdf
>
> The source code (multi01g.cpp, multi01v.cpp, singl01g.cpp,
> singl01v.cpp) can be found in this paper:
>
> http://m-schulze.9mail.de/schulze3.zip
>
> singl01g.cpp and singl01v.cpp are single-threading.
> multi01g.cpp and multi01v.cpp are multi-treading.
>
> singl01g.cpp and multi01g.cpp are for g++.
> singl01v.cpp and multi01v.cpp are for Microsoft Visual C++.
>
> Markus Schulze
>
>
> ----
> Election-Methods mailing list - see http://electorama.com/em for list info
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.electorama.com/pipermail/election-methods-electorama.com/attachments/20170115/92d5b6b2/attachment.htm>