Crossings and Permutations

Biedl, Therese and Brandenburg, Franz J. and Deng, Xiaotie (2006) Crossings and Permutations. In: Graph Drawing 13th International Symposium, GD 2005, September 12-14, 2005, Limerick, Ireland , pp. 1-12 (Official URL: http://dx.doi.org/10.1007/11618058_1).

Full text not available from this repository.

Abstract

We 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.

Item Type:Conference Paper
Additional Information:10.1007/11618058_1
Classifications:G Algorithms and Complexity > G.420 Crossings
ID Code:675

Repository Staff Only: item control page

References

N. Ailon, M. Charikar, and A. Newman.: Aggregating inconsistent information: ranking and clustering. STOC (2005), 684--693.

J.P. Barthelemy, A. Guenoche, and O. Hudry.: Median linear orders: heuristics and a branch and bound algorithm. Europ. J. Oper. Res. 42, (1989), 313--325.

J. Bartholdi III, C.A. Tovey, and M.A. Trick.: Voting schemes for which it can be difficult to tell who won the election. Soc. Choice Welfare 6, (1989), 157--165.

I. Charon, A. Guenoche, O. Hudry, and F. Woirgard.: New results on the computation of median orders. Discrete Math. 165/166 (1997), 139--153

F.Y.L. Chin, X. Deng, Q. Feng, and S. Zhu.: Approximate and dynamic rank aggregation. Theoret. Comput. Sci. 325, (2004), 409--424.

C. Demetrescu and I. Finochi.: Breaking cycles for minimizing crossings. Electronic J. Algorithm Engineering 6, No. 2, (2001).

P. Diaconis and R. Graham.: Spearman's footrule as a measure for disarray. Journal of the Royal Statistical Society, Series B, 39, (1977), 262--268.

G.Di Battista, P. Eades, R. Tamassia, and I.G. Tollis.: Graph Drawing: Algorithms for the Visualization of Graphs. Prentice Hall, (1999).

C. Dwork, R. Kumar, M. Noar, and D. Sivakumar.: Rank aggregation methods for the Web. Proc. WWW10 (2001), 613--622.

P. Eades and N.C. Wormald.: Edge crossings in drawings of bipartite graphs. Algorithmica 11, (1994), 379--403.

G. Even, J. Naor, B. Schieber, and M. Sudan.: Approximating minimum feedback sets and multicuts in directed graphs. Algorithmica 20, (1998), 151--174.

M.R. Garey and D.S. Johnson.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman, San Francisco, (1979).

M.R. Garey and D.S. Johnson.: Crossing number is NP-complete. SIAM J. Alg. Disc. Meth. 4, (1983), 312--316.

M. Jünger and P. Mutzel.: 2-layer straightline crossing minimization: performance of exact and heuristic algorithms. J. Graph Alg. Appl. 1, (1997), 1--25.

M. Kaufmann and D. Wagner (Eds.).: Drawing Graphs: Methods and Models, LNCS 2025, (2001).

J. G. Kemeny.: Mathematics without numbers. Daedalus 88, (1959), 577--591.

X. Munos, W. Unger, and I. Vrto.: One sided crossing minimization is NP-hard for sparse graphs. Proc. GD 2001, LNCS 2265, (2002), 115--123.

J.W. Moon.: Topics on Tournaments. Holt, New York (1968).

H. Nagamochi.: An Improved approximation to the One-Sided Bilayer Drawing. Discr. Comp. Geometry 33(4), (2005), 569--591.

K. Sugiyama, S. Tagawa, and M. Toda.: Methods for visual understanding of hierarchical systems structures. IEEE Trans. SMC 11, (1981), 109--125.

V. Waddle and A. Malhotra: An E \log E line crossing algorithm for leveled graphs. Proc. GD 99, LNCS 1731 (2000), 59--70.

A. Yamaguchi and A. Sugimoto.: An approximation algorithm for the two-layered graph drawing problem. Discrete Comput. Geom. 33, (2005), 565--591.