Approximating the Permanent
From MaRDI portal
0-1 matrixcounting problemsMarkov chainmonomer-dimer systemperfect matchingspermanentrandom generationrandomised approximation schemerapid mixingsimulated annealingstatistical physics
Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Random graphs (graph-theoretic aspects) (05C80) Determinants, permanents, traces, other special matrix functions (15A15) Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.) (60J20) Parallel algorithms in computer science (68W10)
Recommendations
- scientific article; zbMATH DE number 4131659
- 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
Cited in
(only showing first 100 items - show all)- Rates of convergence of some multivariate Markov chains with polynomial eigenfunctions
- Sampling Eulerian orientations of triangular lattice graphs
- Censored Glauber dynamics for the mean field Ising model
- On coupling and the approximation of the permanent
- On the random generation and counting of matchings in dense graphs
- Matching theory -- a sampler: From Dénes König to the present
- Approximating the permanent of graphs with large factors
- Approximating the permanent via importance sampling with application to the dimer covering problem
- Exploration of NP-hard enumeration problems by simulated annealing -- the spectrum values of permanents
- Comparing eigenvalue bounds for Markov chains: When does Poincaré beat Cheeger?
- Polynomial time approximation schemes for dense instances of \( \mathcal{NP}\)-hard problems
- Computational complexity of loss networks
- 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
- Recent developments and problems in the domain of random generation
- Coupling, spectral gap and related topics. II
- The Metropolis algorithm for graph bisection
- Computing the permanent by importance sampling method.
- The electrical resistance of a graph captures its commute and cover times
- Expanding and forwarding parameters of product graphs
- A discipline of evolutionary programming
- Latent semantic indexing: A probabilistic analysis
- Approximating the number of monomer-dimer coverings of a lattice.
- Random cluster dynamics for the Ising model is rapidly mixing
- Spectral gap estimates in mean field spin glasses
- The effect of boundary conditions on mixing of 2D Potts models at discontinuous phase transitions
- T-tetrominoes Tiling's Markov chain mixes fast
- Sampling contingency tables
- The flip Markov chain for connected regular graphs
- The Ising partition function: zeros and deterministic approximation
- Rejection sampling of bipartite graphs with given degree sequence
- Counting hypergraph matchings up to uniqueness threshold
- Glauber dynamics on trees and hyperbolic graphs
- Expanding and forwarding
- An analysis of Monte Carlo algorithm for estimating the permanent
- Markov chain decomposition for convergence rate analysis
- Applications of geometric bounds to the convergence rate of Markov chains on \(\mathbb R^ {n}\).
- On the two-dimensional dynamical Ising model in the phase coexistence region
- Dimension spectrum of Axiom A diffeomorphisms. I: The Bowen-Margulis measure
- Markov chain convergence: From finite to infinite
- A mildly exponential approximation algorithm for the permanent
- Exact thresholds for Ising-Gibbs samplers on general graphs
- A deterministic approximation algorithm for computing the permanent of a 0, 1 matrix
- Mixing times for uniformly ergodic Markov chains
- A faster FPTAS for counting two-rowed contingency tables
- A two-level method for mimetic finite difference discretizations of elliptic problems
- Uniform generation of \(d\)-factors in dense host graphs
- Mixing of Markov chains for independent sets on chordal graphs with bounded separators
- Cutoff for random walk on dynamical Erdős-Rényi graph
- Parameterized counting of partially injective homomorphisms
- A multiscale environment for learning by diffusion
- Zero-freeness and approximation of real Boolean Holant problems
- Sublinear-time distributed algorithms for detecting small cliques and even cycles
- Zeros and approximations of holant polynomials on the complex plane
- Random-cluster dynamics in \(\mathbb{Z}^2\): rapid mixing with general boundary conditions
- The mixing time of switch Markov chains: a unified approach
- Boolean approximate counting CSPs with weak conservativity, and implications for ferromagnetic two-spin
- Convergence time to equilibrium of the Metropolis dynamics for the GREM
- Mixing of permutations by biased transpositions
- Sampling k-partite graphs with a given degree sequence
- A version of Aldous' spectral-gap conjecture for the zero range process
- Linking and cutting spanning trees
- Uniform generation of spanning regular subgraphs of a dense graph
- Spatial mixing and the connective constant: optimal bounds
- A hybrid algorithm for computing permanents of sparse matrices
- Approximating a sequence of observations by a simple process
- On the computational complexity of MCMC-based estimators in large samples
- A note on the relaxation time of two Markov chains on rooted phylogenetic tree spaces
- Simple Monte Carlo and the Metropolis algorithm
- Random bichromatic matchings
- Evolving sets, mixing and heat kernel bounds
- Spectral independence, coupling, and the spectral gap of the Glauber dynamics
- Complexity theory. Abstracts from the workshop held November 14--20, 2021 (hybrid meeting)
- Self-testing algorithms for self-avoiding walks
- Random sampling for the monomer-dimer model on a lattice.
- Analyzing Glauber dynamics by comparison of Markov chains
- Estimating the permanent by importance sampling from a finite population
- A load balancing strategy for parallel computation of sparse permanents.
- A permanent formula with many zero-valued terms
- Approximating the permanent via nonabelian determinants
- Column-wise extendible vector expressions and the relational computation of sets of sets
- Dirichlet eigenvalues, local random walks, and analyzing clusters in graphs
- Some problems on approximate counting in graphs and matroids
- scientific article; zbMATH DE number 4131659 (Why is no real title available?)
- Error bounds for computing the expectation by Markov chain Monte Carlo
- A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries.
- Bravely, moderately: a common theme in four recent works
- scientific article; zbMATH DE number 420886 (Why is no real title available?)
- Decentralized dynamics for finite opinion games
- Generalization of discrete-time geometric bounds to convergence rate of Markov processes on Rn
- Hafnians, perfect matchings and Gaussian matrices
- Sampling Edge Covers in 3-Regular Graphs
- Convergence to equilibrium of logit dynamics for strategic games
- Logarithmic Sobolev, isoperimetry and transport inequalities on graphs
- The first two largest eigenvalues of Laplacian, spectral gap problem and Cheeger constant of graphs
- Mixing of the Glauber dynamics for the ferromagnetic Potts model
- Accelerating Simulated Annealing for the Permanent and Combinatorial Counting Problems
- Counting without sampling: Asymptotics of the log-partition function for certain statistical physics models
- scientific article; zbMATH DE number 3930346 (Why is no real title available?)
- Dynamics of (2+1)-dimensional SOS surfaces above a wall: slow mixing induced by entropic repulsion
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)
