Approximating the Permanent

DOI10.1137/0218077zbMATH Open0723.05107DBLPjournals/siamcomp/JerrumS89OpenAlexW2106285343WikidataQ56386807 ScholiaQ56386807MaRDI QIDQ3211352FDOQ3211352

Authors: Alistair Sinclair, Mark Jerrum 

Publication date: 1989

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0218077

Recommendations

• Publication:3033320
• A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries.
• FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science
• Approximating the permanent: A simple approach
• An analysis of Monte Carlo algorithm for estimating the permanent

zbMATH Keywords

Markov chainsimulated annealingperfect matchingspermanentstatistical physicscounting problemsrandom generation0-1 matrixrapid mixingmonomer-dimer systemrandomised approximation scheme

Mathematics Subject Classification ID

Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.) (60J20) Random graphs (graph-theoretic aspects) (05C80) Determinants, permanents, traces, other special matrix functions (15A15) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Parallel algorithms in computer science (68W10)

Cited In (only showing first 100 items - show all)

• Mixing times for uniformly ergodic Markov chains
• Title not available (Why is that?)
• Dynamics of \((2+1)\)-dimensional SOS surfaces above a wall: slow mixing induced by entropic repulsion
• Title not available (Why is that?)
• Approximating the permanent via importance sampling with application to the dimer covering problem
• Polynomial Time Algorithms to Approximate Permanents and Mixed Discriminants Within a Simply Exponential Factor
• Latent semantic indexing: A probabilistic analysis
• The electrical resistance of a graph captures its commute and cover times
• The expected characteristic and permanental polynomials of the random Gram matrix
• Spatial mixing and the connective constant: optimal bounds
• Approximately counting paths and cycles in a graph
• Estimation of spectral gap for Markov chains
• On the computational complexity of MCMC-based estimators in large samples
• Counting without sampling: Asymptotics of the log-partition function for certain statistical physics models
• Slow droplet-driven relaxation of stochastic Ising models in the vicinity of the phase coexistence region
• Random walks, totally unimodular matrices, and a randomised dual simplex algorithm
• A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries.
• Calculation of the permanent of a sparse positive matrix
• A partially structure-preserving algorithm for the permanents of adjacency matrices of fullerenes
• Sublinear-time distributed algorithms for detecting small cliques and even cycles
• Censored Glauber dynamics for the mean field Ising model
• Column-wise extendible vector expressions and the relational computation of sets of sets
• Convergence to equilibrium of logit dynamics for strategic games
• Exact thresholds for Ising-Gibbs samplers on general graphs
• Approximating the permanent of graphs with large factors
• A note on the relaxation time of two Markov chains on rooted phylogenetic tree spaces
• Finite-size scaling, phase coexistence, and algorithms for the random cluster model on random graphs
• A permanent formula with many zero-valued terms
• Gibbs rapidly samples colorings of \(G(n, d/n)\)
• Polynomial time approximation schemes for dense instances of \( \mathcal{NP}\)-hard problems
• Approximating the number of monomer-dimer coverings of a lattice.
• Evolving sets, mixing and heat kernel bounds
• On quantitative convergence to quasi-stationarity
• Accelerating Simulated Annealing for the Permanent and Combinatorial Counting Problems
• Matchings in vertex-transitive bipartite graphs
• Fast uniform generation of regular graphs
• On the two-dimensional dynamical Ising model in the phase coexistence region
• Matrix permanent and quantum entanglement of permutation invariant states
• Improved Bounds for Mixing Rates of Markov Chains and Multicommodity Flow
• Random sampling for the monomer-dimer model on a lattice.
• Decentralized dynamics for finite opinion games
• The Metropolis algorithm for graph bisection
• Hafnians, perfect matchings and Gaussian matrices
• Matching theory -- a sampler: From Dénes König to the present
• A semidefinite bound for mixing rates of Markov chains
• Markov chain decomposition for convergence rate analysis
• Approximating the permanent: A simple approach
• Nash inequalities for finite Markov chains
• Explicit error bounds for lazy reversible Markov chain Monte Carlo
• Sequential importance sampling for estimating expectations over the space of perfect matchings
• An improved fully polynomial randomized approximation scheme (FPRAS) for counting the number of Hamiltonian cycles in dense digraphs
• A deterministic approximation algorithm for computing the permanent of a 0, 1 matrix
• A hybrid algorithm for computing permanents of sparse matrices
• Logarithmic Sobolev, isoperimetry and transport inequalities on graphs
• Markov-chain monte carlo: Some practical implications of theoretical results
• Tilings of rectangles with T-tetrominoes
• Expanding and forwarding
• Rates of convergence of some multivariate Markov chains with polynomial eigenfunctions
• A mildly exponential approximation algorithm for the permanent
• Approximately counting embeddings into random graphs
• Dimension spectrum of Axiom A diffeomorphisms. I: The Bowen-Margulis measure
• Simulated annealing: A tool for operational research
• Applications of geometric bounds to the convergence rate of Markov chains on \(\mathbb R^ {n}\).
• Comparing eigenvalue bounds for Markov chains: When does Poincaré beat Cheeger?
• A discipline of evolutionary programming
• Glauber dynamics on trees and hyperbolic graphs
• Uniform estimates of nonlinear spectral gaps
• The worm process for the Ising model is rapidly mixing
• Approximating the permanent via nonabelian determinants
• An asymptotic approximation for the permanent of a doubly stochastic matrix
• On the permanents of circulant and degenerate Schur matrices
• Uniform generation of \(d\)-factors in dense host graphs
• Analyzing Glauber dynamics by comparison of Markov chains
• A Mildly Exponential Time Algorithm for Approximating the Number of Solutions to a Multidimensional Knapsack Problem
• Simple Monte Carlo and the Metropolis algorithm
• Spectral gap estimates in mean field spin glasses
• Random path method with pivoting for computing permanents of matrices
• Relation-algebraic computation of fixed points with applications
• Error bounds for computing the expectation by Markov chain Monte Carlo
• Counting restricted homomorphisms via Möbius inversion over matroid lattices
• Random cluster dynamics for the Ising model is rapidly mixing
• Spatial mixing and the random‐cluster dynamics on lattices
• Coupling, spectral gap and related topics. II
• A Randomised Approximation Algorithm for Counting the Number of Forests in Dense Graphs
• The flip Markov chain for connected regular graphs
• Discrete quantitative nodal theorem
• Mixing of permutations by biased transpositions
• A faster FPTAS for counting two-rowed contingency tables
• Computing the permanent by importance sampling method.
• Title not available (Why is that?)
• Sampling Edge Covers in 3-Regular Graphs
• Title not available (Why is that?)
• A two-level method for mimetic finite difference discretizations of elliptic problems
• Title not available (Why is that?)
• Perfect Sampling in Infinite Spin Systems Via Strong Spatial Mixing
• Sampling \(k\)-partite graphs with a given degree sequence
• An Almost m-wise Independent Random Permutation of the Cube
• The Ising partition function: zeros and deterministic approximation
• Graph classes and the switch Markov chain for matchings
• Mixing of the Glauber dynamics for the ferromagnetic Potts model

This page was built for publication: Approximating the Permanent

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3211352)