TY - GEN
T1 - Crossings and permutations
AU - Biedl, Therese
AU - Brandenburg, Franz J.
AU - Deng, Xiaotie
N1 - Publication details (e.g. title, author(s), publication statuses and dates) are captured on an “AS IS” and “AS AVAILABLE” basis at the time of record harvesting from the data source. Suggestions for further amendments or supplementary information can be sent to [email protected].
PY - 2006
Y1 - 2006
N2 - We investigate crossing minimization problems for a set of permutations, where a crossing expresses a disarrangement between elements. The goal is a common permutation π* which minimizes the number of crossings. This is known as the Kemeny optimal aggregation problem minimizing the Kendall-τ 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, 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 crossing minimization is solved by inspecting the drawings, whereas it remains open for three permutations. © Springer-Verlag Berlin Heidelberg 2005.
AB - We investigate crossing minimization problems for a set of permutations, where a crossing expresses a disarrangement between elements. The goal is a common permutation π* which minimizes the number of crossings. This is known as the Kemeny optimal aggregation problem minimizing the Kendall-τ 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, 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 crossing minimization is solved by inspecting the drawings, whereas it remains open for three permutations. © Springer-Verlag Berlin Heidelberg 2005.
UR - https://www.scopus.com/pages/publications/33745651383
UR - https://www.scopus.com/pages/publications/33745651383#tab=impact
U2 - 10.1007/11618058_1
DO - 10.1007/11618058_1
M3 - RGC 32 - Refereed conference paper (with host publication)
SN - 3540314253
SN - 9783540314257
VL - 3843 LNCS
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 1
EP - 12
BT - Graph Drawing - 13th International Symposium, GD 2005, Revised Papers
T2 - 13th International Symposium on Graph Drawing, GD 2005
Y2 - 12 September 2005 through 14 September 2005
ER -