Rankability and Linear Ordering Problem: New Probabilistic Insight and Algorithms
This work addresses the rankability verification problem in LOP, which is incremental as it builds on existing methods with new probabilistic insights and algorithms for moderate-sized datasets.
The paper tackles the problem of verifying whether data are rankable for the linear ordering problem (LOP) by adopting a probabilistic perspective and estimating parameters from pairwise comparisons. It introduces the Slater spectrum and algorithms with complexities O(M^3 2^M) for spectrum computation and O(M 2^M) for finding all LOP solutions, demonstrating them on synthetic and real-world data.
The linear ordering problem (LOP), which consists in ordering M objects from their pairwise comparisons, is commonly applied in many areas of research. While efforts have been made to devise efficient LOP algorithms, verification of whether the data are rankable, that is, if the linear ordering problem (LOP) solutions have a meaningful interpretation, received much less attention. To address this problem, we adopt a probabilistic perspective where the results of pairwise comparisons are modeled as Bernoulli variables with a common parameter and we estimate the latter from the observed data. The brute-force approach to the required enumeration has a prohibitive complexity of O(M !), so we reformulate the problem and introduce a concept of the Slater spectrum that generalizes the Slater index, and then devise an algorithm to find the spectrum with complexity O(M^3 2^M) that is manageable for moderate values of M. Furthermore, with a minor modification of the algorithm, we are able to find all solutions of the LOP with the complexity O(M 2^M). Numerical examples are shown on synthetic and real-world data, and the algorithms are publicly available.