  It is generally believed that the preference ranking method PROMETHEE has a
quadratic time complexity. In this paper, however, we present an exact
algorithm that computes PROMETHEE's net flow scores in time O(qn log(n)), where
q represents the number of criteria and n the number of alternatives. The
method is based on first sorting the alternatives after which the unicriterion
flow scores of all alternatives can be computed in one scan over the sorted
list of alternatives while maintaining a sliding window. This method works with
the linear and level criterion preference functions. The algorithm we present
is exact and, due to the sub-quadratic time complexity, vastly extends the
applicability of the PROMETHEE method. Experiments show that with the new
algorithm, PROMETHEE can scale up to millions of tuples.
