Rankability and linear ordering problem: probabilistic insight and algorithms

DOI10.1016/J.COR.2023.106347MaRDI QIDQ6047898zbMATH OpenFDO

Authors Leszek L. Szczeciński, Harsh Sukheja

Publication date 13 September 2023

Published in Computers \& Operations Research (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2208.03860

zbMATH Keywords

Bayesian estimationcombinatorial optimizationlinear ordering problemrankabilityranking

Mathematics Subject Classification ID

Operations research and management science (90Bxx)

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

Recommendations

• A linear ordering problem with weighted rank
• On the linear ordering problem and the rankability of data
• Fairness and the set of optimal rankings for the linear ordering problem
• Publication:4730974
• The linear ordering problem revisited

Cites work

• A benchmark library and a comparison of heuristic methods for the linear ordering problem
• A generalized approach to maximum likelihood paired comparison ranking
• An updated survey on the linear ordering problem for weighted or unweighted tournaments
• Fairness and the set of optimal rankings for the linear ordering problem
• Maximum likelihood paired comparison ranking by linear programming
• Maximum-likelihood paired comparison rankings
• On the linear ordering problem and the rankability of data
• Probabilistic transitivity in sports
• The linear ordering problem revisited
• The rankability of data
• The rankability of weighted data from pairwise comparisons

Cited in

(3)

• A linear time randomizing algorithm for searching ranked functions
• scientific article; zbMATH DE number 4072701 (Why is no real title available?)
• A supervised learning approach to rankability

This page was built for publication: Rankability and linear ordering problem: probabilistic insight and algorithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6047898)