[EM] finding the beat path winner with just one pass through the ranked pairs

[Andrew Myers]

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