PROMETHEE is not quadratic: An O(qnlog(n)) algorithm

Toon Calders and Dimitri Van Assche

Omega, 2018, vol. 76, issue C, 63-69

Abstract: 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(qnlog(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.

Keywords: Decision support systems; PROMETHEE; Multicriteria; Incremental computing; Multicriteria decision analysis (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0305048317303729
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:jomega:v:76:y:2018:i:c:p:63-69

Ordering information: This journal article can be ordered from
http://www.elsevier.com/wps/find/supportfaq.cws_home/regional
https://shop.elsevie ... _01_ooc_1&version=01

DOI: 10.1016/j.omega.2017.04.003

Access Statistics for this article

Omega is currently edited by B. Lev

More articles in Omega from Elsevier
Bibliographic data for series maintained by Catherine Liu ().