[EM] Schulze STV question

Brian Olson bql at bolson.org
Sun Jan 15 06:10:50 PST 2017


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>


More information about the Election-Methods mailing list