Approximating the permanent: A simple approach
From MaRDI portal
Publication:4286300
DOI10.1002/rsa.3240050208zbMath0795.05089OpenAlexW1967852832MaRDI QIDQ4286300
Publication date: 11 September 1994
Published in: Random Structures & Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1002/rsa.3240050208
Combinatorial aspects of matrices (incidence, Hadamard, etc.) (05B20) Determinants, permanents, traces, other special matrix functions (15A15) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Random matrices (algebraic aspects) (15B52) Directed graphs (digraphs), tournaments (05C20) Eulerian and Hamiltonian graphs (05C45)
Related Items
Reduced word enumeration, complexity, and randomization ⋮ Measure concentration in optimization ⋮ Stochastic enumeration method for counting NP-hard problems ⋮ Random path method with pivoting for computing permanents of matrices ⋮ An improved fully polynomial randomized approximation scheme (FPRAS) for counting the number of Hamiltonian cycles in dense digraphs ⋮ A weighted counting algorithm for the circuit constraint ⋮ Sequential importance sampling for estimating expectations over the space of perfect matchings ⋮ New permanental bounds for Ferrers matrices ⋮ Efficient generation of random derangements with the expected distribution of cycle lengths ⋮ Polynomial Time Algorithms to Approximate Permanents and Mixed Discriminants Within a Simply Exponential Factor ⋮ Solution Counting Algorithms for Constraint-Centered Search Heuristics ⋮ An upper bound for the permanent of \((0,1)\)-matrices. ⋮ A partially structure-preserving algorithm for the permanents of adjacency matrices of fullerenes ⋮ Solution counting algorithms for constraint-centered search heuristics ⋮ Estimating the permanent by importance sampling from a finite population ⋮ Clifford algebras and approximating the permanent ⋮ Approximately Counting Embeddings into Random Graphs ⋮ Scaling matrices and counting the perfect matchings in graphs ⋮ Matrix permanent and quantum entanglement of permutation invariant states ⋮ An analysis of Monte Carlo algorithm for estimating the permanent ⋮ An algorithmic proof of Brégman–Minc theorem ⋮ Approximating the number of monomer-dimer coverings of a lattice.
Cites Work
