A survey on the linear ordering problem for weighted or unweighted tournaments (Q2644372)

A relation \(R\) defined on a finite set \(X\) of \(n\) elements (that may represent different teams or alternatives, for example) is a preference relation if for each pair of distinct elements \(u\) and \(v\) either \(uRv\) or \(vRu\), but not both. Let there be given a collection \(P\) of \(m\) preference relations on the same set \(X\). The general linear ordering problem is to determine a single linear order \(O\) with the property that the total number of disagreements between \(O\) and the preferences in \(P\) is minimized. (There may or may not be weights associated with the preferences to be taken into account.) The authors survey work done on various formulations of this and related problems, both when \(m=1\) and in general. In particular, they present complexity results and bounds and discuss various algorithms that have been developed for treating these problems.