# On the Linear Ordering Problem and the Rankability of Data

arXiv: https://arxiv.org/abs/2104.05816 · HTML: https://mlsanity.com/paper/2104.05816/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 1 of its 35 references that are in the map.
- First posted on arXiv 12 Apr 2021.

## Builds on (most cited first, 1 of 1)

- [Diameter Polytopes of Feasible Binary Programs](https://mlsanity.com/paper/2008.06844/) (2020)

## Built on by (most cited first, 6 of 6)

- [Neural Combinatorial Optimization: a New Player in the Field](https://mlsanity.com/paper/2205.01356/) (2022)
- [Neural Improvement Heuristics for Graph Combinatorial Optimization Problems](https://mlsanity.com/paper/2206.00383/) (2022)
- [DiversiTree: A New Method to Efficiently Compute Diverse Sets of Near-Optimal Solutions to Mixed-Integer Optimization Problems](https://mlsanity.com/paper/2204.03822/) (2022)
- [Rankability and Linear Ordering Problem: New Probabilistic Insight and Algorithms](https://mlsanity.com/paper/2208.03860/) (2022)
- [SUMMIR: A Hallucination-Aware Framework for Ranking Sports Insights from LLMs](https://mlsanity.com/paper/2604.04947/) (2026)
- [Linear Ordering Problem: Time for a Change](https://mlsanity.com/paper/2605.31051/) (2026)

## Abstract (arXiv)

In 2019, Anderson et al. proposed the concept of rankability, which refers to a dataset's inherent ability to be meaningfully ranked. In this article, we give an expository review of the linear ordering problem (LOP) and then use it to analyze the rankability of data. Specifically, the degree of linearity is used to quantify what percentage of the data aligns with an optimal ranking. In a sports context, this is analogous to the number of games that a ranking can correctly predict in hindsight. In fact, under the appropriate objective function, we show that the optimal rankings computed via the LOP maximize the hindsight accuracy of a ranking. Moreover, we develop a binary program to compute the maximal Kendall tau ranking distance between two optimal rankings, which can be used to measure the diversity among optimal rankings without having to enumerate all optima. Finally, we provide several examples from the world of sports and college rankings to illustrate these concepts and demonstrate our results.