[EM] Schulze STV question

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


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:


The source code (multi01g.cpp, multi01v.cpp, singl01g.cpp,
singl01v.cpp) can be found in this paper:


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