Fast approximation of the permanent for very dense problems

ABSTRACT

Approximation of the permanent of a matrix with nonnegative entries is a well studied problem. The most successful approach to date for general matrices uses Markov chains to approximately sample from a distribution on weighted permutations, and Jerrum, Sinclair, and Vigoda developed such a method they proved runs in polynomial time in the input. The current bound on the running time of their method is O(n⁷(log n)⁴). Here we present a very different approach using sequential acceptance/rejection, and show that for a class of dense problems this method has an O(n⁴ log n) expected running time.

REFERENCES

• 1: R. Ahuja, T. Magnanti, and J. Orlin, Network Flows, Prentice Hall, 1993.
• 2: Alexander Barvinok, Polynomial time algorithms to approximate permanents and mixed discriminants within a simply exponential factor, Random Structures & Algorithms, v.14 n.1, p.29-61, Jan. 1999 [doi>10.1002/(SICI)1098-2418(1999010)14:1<29::AID-RSA2>3.0.CO;2-X]
• 3: Ivona Bezáková , Daniel Štefankovič , Vijay V. Vazirani , Eric Vigoda, Accelerating simulated annealing for the permanent and combinatorial counting problems, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.900-907, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109656]
• 4: L. M. Bregman, Some properties of nonnegative matrices and their permanents, Soviet. Math. Dokl., 14 (1973), pp. 945--949.
• 5: A Z Broder, How hard is it to marry at random? (On the approximation of the permanent), Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.50-58, May 28-30, 1986, Berkeley, California, United States [doi>10.1145/12130.12136]
• 6: P. Diaconis and D. Stroock, Geometric bounds for eigenvalues of Markov chains, Ann. Appl. Probab., 1 (1991), pp. 36--61.
• 7: B. Efron and V. Petrosian, Nonparametric Methods for Doubly Truncated Data, J. Amer. Statist. Assoc., 94 (1999), pp. 824--834.
• 8: G. P. Egorychev, The solution of van der Waerden's problem for pemanents, Advances in Math., 42 (1981), pp. 299--305.
• 9: D. I. Falikman, Proof of the van der Waerden's conjecture on the permanent of a doubly stochastic matrix, Mat. Zametki, 29 (1981), pp. 931--938.
• 10: G. S. Fishman, Choosing sample path length and number of sample paths when starting in the steady state, Oper. Res. Letters, 16 (1994), pp. 209--219.
• 11: J. E. Hopcroft and R. M. Karp, An n^5/2 Algorithm for Maximum Matchings in Bipartite Graphs, SIAM J. Comput., 2 (1973), pp. 225--231.
• 12: Mark Huber, Exact Sampling from Perfect Matchings of Dense Regular Bipartite Graphs, Algorithmica, v.44 n.3, p.183-193, April 2006 [doi>10.1007/s00453-005-1175-9]
• 13: M. Jerrum , Alistair Sinclair, Approximating the permanent, SIAM Journal on Computing, v.18 n.6, p.1149-1178, Dec. 1989 [doi>10.1137/0218077]
• 14: M. Jerrum and A. Sinclair, The Markov Chain Monte Carlo Method: An Approach to Approximate Counting and Integration, PWS Publishing, 1996.
• 15: M R Jerrum , L G Valiant , V V Vazirani, Random generation of combinatorial structures from a uniform, Theoretical Computer Science, v.43 n.2-3, p.169-188, July 1986
• 16: M. Jerrum and U. V. Vazirani, A Mildly Exponential Approximation Algorithm for the Permanent, Algorithmica, 16 (1996), pp. 392--401.
• 17: Mark Jerrum , Alistair Sinclair , Eric Vigoda, A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries, Journal of the ACM (JACM), v.51 n.4, p.671-697, July 2004 [doi>10.1145/1008731.1008738]
• 18: B. Kalantari and L. Khachiyan, On the Complexity of Nonnegative-Matrix Scalings, Linear Algebra Appl., 240 (1996), pp. 87--103.
• 19: P. W. Kasteleyn, The statistics of dimers on a lattice, I., The number of dimer arrangements on a quadratic lattice, Physica, 27 (1961), pp. 1664--1672.
• 20: N. Linial, A. Samorodnitsky, and A. Wigderson, A deterministic strongly polynomial algorithm for matrix scaling and approximate permanents, Combinatorica, 20 (2000), pp. 545--568.
• 21: J. H. Van Lint and R. M. Wilson, A Course in Combinatorics, Cambridge University Press, 1992.
• 22: H. Minc, Upper bounds for permanents of (0,1)-matrices, Bull. Amer. Math. Soc., 69 (1963), pp. 789--791.
• 23: Rajeev Motwani , Prabhakar Raghavan, Randomized algorithms, Cambridge University Press, New York, NY, 1995
• 24: Hanna Pasula , Stuart J. Russell , Michael Ostland , Yaacov Ritov, Tracking Many Objects with Many Sensors, Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence, p.1160-1171, July 31-August 06, 1999
• 25: R. Sinkhorn, A relationship between arbitrary positive matrices and double stochastic matrices, A., Math. Statist., 35 (1964), pp. 876--879.
• 26: G. W. Soules, Extending the Minc-Bregman upper bound for the permanent, Linear and Multilinear Algebra, 47 (2000), pp. 77--91.
• 27: L. G. Valiant, The complexity of computing the permanent, Theoret. Comput. Sci., 8 (1979), pp. 189--201.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations on matrices

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.2 Approximation
          Subjects: Linear approximation
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Permutations and combinations
  G.3 PROBABILITY AND STATISTICS
      Subjects: Markov processes

General Terms:
Algorithms, Design, Theory