论文标题
排名性和线性排序问题：新的概率洞察力和算法
Rankability and Linear Ordering Problem: New Probabilistic Insight and Algorithms
论文作者
论文摘要
线性排序问题（LOP）包括从成对比较中订购M对象，通常用于许多研究领域。尽管已经努力设计有效的LOP算法，但验证数据是否可以排名，也就是说，如果线性订购问题（LOP）解决方案具有有意义的解释，则受到了较少的关注。为了解决这个问题，我们采用概率的观点，其中成对比较的结果被建模为具有共同参数的伯努利变量，并且我们从观察到的数据中估算了后者。对所需枚举的野蛮手法的方法具有O（m！）的过度复杂性，因此我们重新重新重新重新制定了Slater频谱的概念，该概念将Slater索引概括，然后设计一个算法，然后设计具有复杂性O（M^3 2^m）的频谱，以使所有M.的求解都可以控制。具有复杂性O（m 2^m）的LOP的。数值示例显示在合成和现实世界数据上，并且算法可公开使用。
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.
