## Crossings and Permutations
Biedl, Therese and Brandenburg, Franz J. and Deng, Xiaotie
(2006)
Full text not available from this repository. ## AbstractWe investigate crossing minimization problems for a set of permutations, where a crossing expresses a disarrangement between elements. The goal is a common permutation pi which minimizes the number of crossings. This is known as the Kemeny optimal aggregation problem minimizing the Kendall-tau distance. Recent interest into this problem comes from application to meta-search and spam reduction on the Web. This rank aggregation problem can be phrased as a one-sided two-layer crossing minimization problem for an edge coloured bipartite graph, where crossings are counted only for monochromatic edges. Here we introduce the max-version of the crossing minimization problem, PCM_{max}-k, which attempts to minimize the discrimination against any permutation. We show the NP-hardness of the common and the max version for k >= 4 permutations (and k even), and establish a 2-2/k and a 2-approximation, respectively. For two permutations the problem is solved merely by inspecting the drawings, whereas it remains open for three permutations.
Repository Staff Only: item control page References |