Majority Decisions and Transitivity: Some Special Cases

The problem considered is that of obtaining majority decisions which are transitive. We show that the corresponding optimization problems for the weighted l₁ norm and the weighted l₂ norm are identical. We then show that she general problem of minimizing the weighted l_k norm can be equivalently formulated as a set covering problem. Finally, we identify the Tchebycheff problem (l₂ norm) with a class, of bottleneck quadratic assignment problems and give an efficient algorithm for solving it.