On the linear ordering problem and the rankability of data

DOI10.3934/FODS.2021010MaRDI QIDQ2072628zbMATH OpenOpenAlexFDO

Authors Thomas R. Cameron, Sebastian Charmot, Jonad Pulaj

Publication date 26 January 2022

Published in Foundations of Data Science (Search for Journal in Brave)

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

zbMATH Keywords

degree of linearityKendall tau distancelinear ordering problemrankabilityvalid inequalities

Mathematics Subject Classification ID

Boolean programming (90C09) Combinatorial optimization (90C27) Programming involving graphs or networks (90C35)

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

Recommendations

• On the graph Laplacian and the rankability of data
• The rankability of data
• The rankability of weighted data from pairwise comparisons
• Fairness and the set of optimal rankings for the linear ordering problem
• scientific article; zbMATH DE number 4072701

Cites work

• A Cutting Plane Algorithm for the Linear Ordering Problem
• A new heuristic algorithm solving the linear ordering problem
• A NEW MEASURE OF RANK CORRELATION
• A note on small linear-ordering polytopes
• Branch-and-price: Column generation for solving huge integer programs
• Enriching Solutions to Combinatorial Problems via Solution Engineering
• Facets of the linear ordering polytope
• Finding multiple solutions to general integer linear programs
• Heuristic algorithms for the maximum diversity problem
• scientific article; zbMATH DE number 3644821 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 3895002 (Why is no real title available?)
• On the acyclic subgraph polytope
• On the graph Laplacian and the rankability of data
• Optimal Weighted Ancestry Relationships
• The linear ordering problem. Exact and heuristic methods in combinatorial optimization.
• The rankability of data
• The rankability of weighted data from pairwise comparisons

Cited in

(8)

• Ranking functions and axioms for linear orders
• The rankability of weighted data from pairwise comparisons
• scientific article; zbMATH DE number 4072701 (Why is no real title available?)
• A linear ordering of a multi-parameter universe is usually nonsense
• The rankability of data
• Rankability and linear ordering problem: probabilistic insight and algorithms
• Matrix rationalization via partial orders
• Multiple linear ordering problem

Describes a project that uses

Uses Software

• SCIP
• Gurobi
• CPLEX

This page was built for publication: On the linear ordering problem and the rankability of data

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