Crossings and PermutationsBiedl, Therese and Brandenburg, Franz J. and Deng, Xiaotie (2006) Crossings and Permutations. In: Graph Drawing 13th International Symposium, GD 2005, September 1214, 2005 , pp. 112(Official URL: http://dx.doi.org/10.1007/11618058_1). Full text not available from this repository.
Official URL: http://dx.doi.org/10.1007/11618058_1
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 Kendalltau distance. Recent interest into this problem comes from application to metasearch and spam reduction on the Web. This rank aggregation problem can be phrased as a onesided twolayer crossing minimization problem for an edge coloured bipartite graph, where crossings are counted only for monochromatic edges. Here we introduce the maxversion of the crossing minimization problem, PCM_{max}k, which attempts to minimize the discrimination against any permutation. We show the NPhardness of the common and the max version for k >= 4 permutations (and k even), and establish a 22/k and a 2approximation, respectively. For two permutations the problem is solved merely by inspecting the drawings, whereas it remains open for three permutations.
Actions (login required)
