[EM] Schulze STV question

Markus Schulze markus.schulze at alumni.tu-berlin.de
Sun Jan 15 04:21:12 PST 2017


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



More information about the Election-Methods mailing list