Approximating the Permanent
From MaRDI portal
Markov chainsimulated annealingperfect matchingspermanentstatistical physicscounting problemsrandom generation0-1 matrixrapid mixingmonomer-dimer systemrandomised approximation scheme
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)
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
Cited in
(only showing first 100 items - show all)- A Randomised Approximation Algorithm for Counting the Number of Forests in Dense Graphs
- Error bounds for computing the expectation by Markov chain Monte Carlo
- Discrete quantitative nodal theorem
- A faster FPTAS for counting two-rowed contingency tables
- Computing the permanent by importance sampling method.
- Counting restricted homomorphisms via Möbius inversion over matroid lattices
- Mixing of permutations by biased transpositions
- Dynamics of (2+1)-dimensional SOS surfaces above a wall: slow mixing induced by entropic repulsion
- Mixing times for uniformly ergodic Markov chains
- scientific article; zbMATH DE number 7559089 (Why is no real title available?)
- Sampling Edge Covers in 3-Regular Graphs
- scientific article; zbMATH DE number 420886 (Why is no real title available?)
- A two-level method for mimetic finite difference discretizations of elliptic problems
- scientific article; zbMATH DE number 3930346 (Why is no real title available?)
- scientific article; zbMATH DE number 1775454 (Why is no real title available?)
- Sampling \(k\)-partite graphs with a given degree sequence
- scientific article; zbMATH DE number 1369835 (Why is no real title available?)
- Approximating the permanent via importance sampling with application to the dimer covering problem
- Perfect Sampling in Infinite Spin Systems Via Strong Spatial Mixing
- An Almost m-wise Independent Random Permutation of the Cube
- Latent semantic indexing: A probabilistic analysis
- The expected characteristic and permanental polynomials of the random Gram matrix
- The Ising partition function: zeros and deterministic approximation
- The electrical resistance of a graph captures its commute and cover times
- Polynomial Time Algorithms to Approximate Permanents and Mixed Discriminants Within a Simply Exponential Factor
- Approximately counting paths and cycles in a graph
- Spatial mixing and the connective constant: optimal bounds
- Mixing of the Glauber dynamics for the ferromagnetic Potts model
- Linking and cutting spanning trees
- Graph classes and the switch Markov chain for matchings
- Uniform generation of spanning regular subgraphs of a dense graph
- Zeros and approximations of holant polynomials on the complex plane
- scientific article; zbMATH DE number 7559110 (Why is no real title available?)
- Dirichlet eigenvalues, local random walks, and analyzing clusters in graphs
- On the computational complexity of MCMC-based estimators in large samples
- Rejection sampling of bipartite graphs with given degree sequence
- Counting hypergraph matchings up to uniqueness threshold
- Slow droplet-driven relaxation of stochastic Ising models in the vicinity of the phase coexistence region
- Estimation of spectral gap for Markov chains
- Random walks, totally unimodular matrices, and a randomised dual simplex algorithm
- Counting over non-planar graphs
- Counting without sampling: Asymptotics of the log-partition function for certain statistical physics models
- Counting perfect matchings and the switch chain
- The diameter of the uniform spanning tree of dense graphs
- Calculation of the permanent of a sparse positive matrix
- A partially structure-preserving algorithm for the permanents of adjacency matrices of fullerenes
- A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries.
- Sublinear-time distributed algorithms for detecting small cliques and even cycles
- Censored Glauber dynamics for the mean field Ising model
- Markov chain convergence: From finite to infinite
- Estimating the permanent by importance sampling from a finite population
- Convergence to equilibrium of logit dynamics for strategic games
- Swendsen-Wang dynamics for the ferromagnetic Ising model with external fields
- On the Complexity of Holant Problems
- On coupling and the approximation of the permanent
- Column-wise extendible vector expressions and the relational computation of sets of sets
- Approximating the permanent of graphs with large factors
- Exact thresholds for Ising-Gibbs samplers on general graphs
- Mixing artificial and natural intelligence: from statistical mechanics to AI and back to turbulence
- Multiconsistency and robustness with global constraints
- A note on the relaxation time of two Markov chains on rooted phylogenetic tree spaces
- Conductance bounds on the L2 convergence rate of Metropolis algorithms on unbounded state spaces
- A permanent formula with many zero-valued terms
- Generalized dominoes tiling's Markov chain mixes fast
- The complexity of approximating the matching polynomial in the complex plane
- Expanding and forwarding parameters of product graphs
- Finite-size scaling, phase coexistence, and algorithms for the random cluster model on random graphs
- Spectral independence in high-dimensional expanders and applications to the hardcore model
- Polynomial time approximation schemes for dense instances of \( \mathcal{NP}\)-hard problems
- The mixing time of switch Markov chains: a unified approach
- Mixing of Markov chains for independent sets on chordal graphs with bounded separators
- Spectral independence via stability and applications to Holant-type problems
- Gibbs rapidly samples colorings of \(G(n, d/n)\)
- Some problems on approximate counting in graphs and matroids
- Algebraic and combinatorial expansion in random simplicial complexes
- Approximating the number of monomer-dimer coverings of a lattice.
- Matchings in vertex-transitive bipartite graphs
- Evolving sets, mixing and heat kernel bounds
- Fast uniform generation of regular graphs
- Efficient sampling and counting algorithms for the Potts model on ℤd at all temperatures
- Smoothed counting of 0–1 points in polyhedra
- Accelerating Simulated Annealing for the Permanent and Combinatorial Counting Problems
- Perfect sampling from spatial mixing
- On quantitative convergence to quasi-stationarity
- On the two-dimensional dynamical Ising model in the phase coexistence region
- Clifford algebras and approximating the permanent
- Zero-freeness and approximation of real Boolean Holant problems
- Matrix permanent and quantum entanglement of permutation invariant states
- Improved Bounds for Mixing Rates of Markov Chains and Multicommodity Flow
- Parameterized counting of partially injective homomorphisms
- ON THE COMPLEXITY OF COUNTING FIXED POINTS AND GARDENS OF EDEN IN SEQUENTIAL DYNAMICAL SYSTEMS ON PLANAR BIPARTITE GRAPHS
- Self-testing algorithms for self-avoiding walks
- A Polynomial-Time Approximation Algorithm for All-Terminal Network Reliability
- Random sampling for the monomer-dimer model on a lattice.
- Decentralized dynamics for finite opinion games
- Hafnians, perfect matchings and Gaussian matrices
- Matching theory -- a sampler: From Dénes König to the present
- The Metropolis algorithm for graph bisection
- A semidefinite bound for mixing rates of Markov chains
- Approximability of the eight-vertex 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)
