On 7/22/64 2:59 PM, Rob LeGrand wrote:
Markus wrote:
the runtime to calculate the strongest path from
every candidate to every other candidate is O(C^3).
However, the runtime to sort O(C^2) pairwise defeats
is already O(C^4). So you cannot get a faster
algorithm by sorting the pairwise defeats.
Can't you sort O(C^2) items in O(C^2 log C) time if you use a O(n log n)
algorithm such as heapsort?
Yes, this is correct. In practice quicksort is faster than heapsort
(though not asymptotically).
The strongest path algorithm is solved in O(C^3) using the
Floyd-Warshall algorithm, applied to a different commutative semiring
(max, min) than the usual (min, +). However, faster algorithms are
known for solving the same problem (all-pairs shortest path).
For example, there is a paper by Melhorn and Priebe that shows how to
solve it in O(C^2 log C) expected time. I don' t know if these faster
algorithms work on all commutative semirings, though.
-- Andrew
----
Election-Methods mailing list - see http://electorama.com/em for list info
