Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

Sets of permutations play an important role in the design of some efficient algorithms. In this paper we design two algorithms that manipulate sets of permutations. Both algorithms, each solving a different problem, use fast matrix multiplication techniques to achieve a significant improvement in the running time over the naive solutions.

For a set of permutations P ⊂ S_n we say that i k-dominates j if the number of permutations π ∈ P for which π(i) < π(j) is k. The dominance matrix of P is the n x n matrix D_P where D_P(i, j) = k if and only if i k-dominates j. We give an efficient algorithm for computing D_P using fast rectangular matrix multiplication. In particular, when |P| = n our algorithm runs in O(n^2.684) time. Computing the dominance matrix of permutations is computationally equivalent to the dominance problem in computational geometry. Thus, our algorithm slightly improves upon a well-known O(n^2.688) time algorithm of Matousek for the dominance problem. Permutation dominance is used, together with several other ingredients, to obtain a truly sub-cubic algorithm for the All Pairs Shortest Paths (APSP) problem in real-weighted directed graphs, where the number of distinct weights emanating from each vertex is O(n^0.338). A special case of this algorithm implies an O(n^2.842) time algorithm for real vertex-weighted APSP, which slightly improves a recent result of Chan [STOC-07].

A set of permutations P ⊂ S_n is fully expanding if the product of any two elements of P yields a distinct permutation. Stated otherwise, |P²| = |P|² where P² ⊂ S_n is the set of products of two elements of P. We present a randomized algorithm that computes |P²| and hence decides if P is fully expanding. The algorithm also produces a table that, for any σ₁, σ₂, σ₃, σ₄ ∈ P, answers the query σ₁σ₂ = σ₃σ₄ in Õ(1) time. The algorithm uses, among other ingredients, a combination of fast matrix multiplication and polynomial identity testing. In particular, for |P| = n our algorithm runs in O(n^ω) time where ω < 2.376 is the matrix multiplication exponent. We note that the naive deterministic solution for this problem requires Θ(n³) time.

REFERENCES

• 1: N. Alon, Generating pseudo-random permutations and maximum flow algorithms, Information Processing Letters, v.35 n.4, p.201-204, Aug. 1990 [doi>10.1016/0020-0190(90)90024-R]
• 2: N. Alon and M. Naor, Derandomization, witnesses for Boolean matrix multiplication and construction of perfect hash functions, Algorithmica, 16 (1996), pp. 434--449.
• 3: Andrei Z. Broder , Moses Charikar , Michael Mitzenmacher, A derandomization using min-wise independent permutations, Journal of Discrete Algorithms, v.1 n.1, p.11-20, February 2003 [doi>10.1016/S1570-8667(03)00003-0]
• 4: T. M. Chan, All Pairs Shortest Paths with Real Weights in O(n³ / log n) Time, Proceedings of the 9^th Workshop on Algorithms and Data Structures (WADS), Lecture Notes in Computer Science, 3608 (2005), pp. 318--324.
• 5: Timothy M. Chan, More algorithms for all-pairs shortest paths in weighted graphs, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA [doi>10.1145/1250790.1250877]
• 6: Don Coppersmith, Rectangular matrix multiplication revisited, Journal of Complexity, v.13 n.1, p.42-49, March 1997 [doi>10.1006/jcom.1997.0438]
• 7: Don Coppersmith , Shmuel Winograd, Matrix multiplication via arithmetic progressions, Journal of Symbolic Computation, v.9 n.3, p.251-280, March 1990 [doi>10.1016/S0747-7171(08)80013-2]
• 8: M. L. Fredman, New bounds on the complexity of the shortest path problem, SIAM Journal on Computing, 5 (1976), pp. 49--60.
• 9: Zvi Galil , Oded Margalit, Witnesses for Boolean matrix multiplication and for transitive closure, Journal of Complexity, v.9 n.2, p.201-221, June 1993 [doi>10.1006/jcom.1993.1014]
• 10: Xiaohan Huang , Victor Y. Pan, Fast rectangular matrix multiplication and applications, Journal of Complexity, v.14 n.2, p.257-299, June 1, 1998 [doi>10.1006/jcom.1998.0476]
• 11: Jiří Matoušek, Computing dominances inEn (short communication), Information Processing Letters, v.38 n.5, p.277-278, June 14, 1991 [doi>10.1016/0020-0190(91)90071-O]
• 12: J. T. Schwartz, Fast Probabilistic Algorithms for Verification of Polynomial Identities, Journal of the ACM (JACM), v.27 n.4, p.701-717, Oct. 1980 [doi>10.1145/322217.322225]
• 13: Virginia Vassilevska , Ryan Williams, Finding a maximum weight triangle in n^3-Δ time, with applications, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA [doi>10.1145/1132516.1132550]
• 14: Virginia Vassilevska , Ryan Williams , Raphael Yuster, All-pairs bottleneck paths for general graphs in truly sub-cubic time, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA [doi>10.1145/1250790.1250876]
• 15: Richard Zippel, Probabilistic algorithms for sparse polynomials, Proceedings of the International Symposiumon on Symbolic and Algebraic Computation, p.216-226, June 01, 1979
• 16: All pairs shortest paths using bridging sets and rectangular matrix multiplication, Journal of the ACM (JACM), v.49 n.3, p.289-317, May 2002 [doi>10.1145/567112.567114]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Combinatorial algorithms

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Permutations and combinations

  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Analysis of algorithms