Finding a ranking which minimizes the number of conflicts Suppose that $k$ different voters have each produced a partial ordering of candidates $1,\ldots,n$. For example, if $k=3$ and $n=4$, the voters may have produced the partial orders


$1&lt;2$
$2&lt;1&lt;3&lt;4$
$2&lt;3&lt;1$


Our goal is to fuse all these into a single ranking of the candidates in a way that minimizes conflicts. The following seems like a natural way to do this. Given a total order $L$, let $C(i,j)$ be the number of the partial orders which rank $i$ and $j$ in the opposite way from $L$ (i.e., if $L$ ranks $i$ before $j$, $C(i,j)$ equals the number among the $k$ partial orders that rank $j$ before $i$).  We seek to find a total order $L$ which minimizes $\sum_{i&lt;j} C(i,j)$.

This seems like it would be a well-studied problem, but I have been unable to find any references, likely because I'm not aware of the right keywords. Can any one point me towards papers where algorithms for this problem were considered?
This is a special case of metric $1$-medians, where the metric space is $S_n$ (the symmetric group on $n$ elements) with distance function number of inversions (i.e. the distance between two permutations is the number of pairs $i, j: i&lt;j$ s.t. $i$ and $j$ are ordered differently). This distance metric is also known as Kemeny distance and is related to the weak Bruhat order. 

This paper by Ailon, Charikar, and Newman considers this and related problems. The problem you're asking about is called Rank Aggregation in their paper. Look at their intro for more references. The problem is NP-hard. A simple 2-approximation is to pick the best of the given $k$ permutations (i.e. the permutation that minimizes the objective function). Here is a proof:

Let $\pi$ be the optimal permutation and $\pi_{j^*}$ the best of $\pi_1, \ldots, \pi_k$. For any $i, j \in [k]$, by the triangle inequality, $d(\pi_i, \pi) + d(\pi_j, \pi) \geq d(\pi_i, \pi_j)$. Sum over all $i, j$, and you get $2n\mathsf{OPT} \geq \sum_j{\mathsf{ALG}(j)}$, where $\mathsf{ALG(j)}$ is the cost of choosing $\pi_j$ as the solution, and $\mathsf{OPT}$ is the cost of the optimal solution. Since $\pi_{j^*}$ was chosen so that $\mathsf{ALG}(j^*)$ is minimum over all $\mathsf{ALG}(j)$ for $j \in [k]$, we have $\mathsf{ALG}(j^*) \leq \sum_j{\mathsf{ALG}(j)} /n$ and we have $\mathsf{ALG}(j^*) \leq 2\mathsf{OPT}$.

The paper I referred you to above has another, almost equally simple 2-approximation (but the proof is not that simple, though still not bad). They can show that the bad cases for the two approximation algorithms are different, and taking the better solution of the two gives 11/7 approximation factor. 

Then there is also a PTAS by Mathieu and Schudy (Warren sometimes visits this site btw), by a reduction to weighted Minimum Feedback Arc Set in Tournamets (the same reduction is used in the previous paper, I think). Here is the link