Approximating the Permanent

DOI10.1137/0218077zbMath0723.05107OpenAlexW2106285343WikidataQ56386807 ScholiaQ56386807MaRDI QIDQ3211352

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

zbMATH Keywords

simulated annealing Markov chain statistical physics permanent random generation perfect matchings counting problems 0-1 matrix rapid mixing monomer-dimer system randomised approximation scheme

Mathematics Subject Classification ID

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) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Parallel algorithms in computer science (68W10)

Related Items

Slow droplet-driven relaxation of stochastic Ising models in the vicinity of the phase coexistence region, Markov chain decomposition for convergence rate analysis, Spatial mixing and the connective constant: optimal bounds, Discrete quantitative nodal theorem, Random walks, totally unimodular matrices, and a randomised dual simplex algorithm, Applications of geometric bounds to the convergence rate of Markov chains on \(\mathbb R^ {n}\)., A permanent formula with many zero-valued terms, A hybrid algorithm for computing permanents of sparse matrices, Zero-freeness and approximation of real Boolean Holant problems, Decentralized dynamics for finite opinion games, Recent developments and problems in the domain of random generation, Hafnians, perfect matchings and Gaussian matrices, Sublinear-time distributed algorithms for detecting small cliques and even cycles, Approximating a sequence of observations by a simple process, Random cluster dynamics for the Ising model is rapidly mixing, Convergence to equilibrium of logit dynamics for strategic games, Logarithmic Sobolev, isoperimetry and transport inequalities on graphs, On the computational complexity of MCMC-based estimators in large samples, Multiconsistency and robustness with global constraints, On the two-dimensional dynamical Ising model in the phase coexistence region, Dimension spectrum of Axiom A diffeomorphisms. I: The Bowen-Margulis measure, Spectral gap estimates in mean field spin glasses, The effect of boundary conditions on mixing of 2D Potts models at discontinuous phase transitions, Random path method with pivoting for computing permanents of matrices, Tilings of rectangles with T-tetrominoes, Markov chain convergence: From finite to infinite, Zeros and approximations of holant polynomials on the complex plane, Coupling, spectral gap and related topics. II, Column-Wise Extendible Vector Expressions and the Relational Computation of Sets of Sets, A mildly exponential approximation algorithm for the permanent, The Metropolis algorithm for graph bisection, Dirichlet Eigenvalues, Local Random Walks, and Analyzing Clusters in Graphs, Random-cluster dynamics in \(\mathbb{Z}^2\): rapid mixing with general boundary conditions, Computing the permanent by importance sampling method., The electrical resistance of a graph captures its commute and cover times, Spectral independence, coupling, and the spectral gap of the Glauber dynamics, Dynamics of \((2+1)\)-dimensional SOS surfaces above a wall: slow mixing induced by entropic repulsion, The expected characteristic and permanental polynomials of the random Gram matrix, An improved fully polynomial randomized approximation scheme (FPRAS) for counting the number of Hamiltonian cycles in dense digraphs, The complexity of power indexes with graph restricted coalitions, T-tetrominoes Tiling's Markov chain mixes fast, Exact thresholds for Ising-Gibbs samplers on general graphs, Complexity theory. Abstracts from the workshop held November 14--20, 2021 (hybrid meeting), Fast uniform generation of regular graphs, Simulated annealing: A tool for operational research, Sampling contingency tables, Expanding and forwarding parameters of product graphs, A deterministic approximation algorithm for computing the permanent of a 0, 1 matrix, A note on the relaxation time of two Markov chains on rooted phylogenetic tree spaces, The flip Markov chain for connected regular graphs, Mixing times for uniformly ergodic Markov chains, The Ising partition function: zeros and deterministic approximation, Rejection sampling of bipartite graphs with given degree sequence, Uniform estimates of nonlinear spectral gaps, Counting hypergraph matchings up to uniqueness threshold, Simple Monte Carlo and the Metropolis algorithm, A faster FPTAS for counting two-rowed contingency tables, The mixing time of switch Markov chains: a unified approach, Self-testing algorithms for self-avoiding walks, Analyzing Glauber dynamics by comparison of Markov chains, Matchings in vertex-transitive bipartite graphs, The worm process for the Ising model is rapidly mixing, Nash inequalities for finite Markov chains, On the permanents of circulant and degenerate Schur matrices, Approximately counting paths and cycles in a graph, Matching theory -- a sampler: From Dénes König to the present, Random bichromatic matchings, A two-level method for mimetic finite difference discretizations of elliptic problems, Uniform generation of \(d\)-factors in dense host graphs, Calculation of the permanent of a sparse positive matrix, A partially structure-preserving algorithm for the permanents of adjacency matrices of fullerenes, Mixing of Markov chains for independent sets on chordal graphs with bounded separators, Estimating the permanent by importance sampling from a finite population, Glauber dynamics on trees and hyperbolic graphs, Cutoff for random walk on dynamical Erdős-Rényi graph, Parameterized counting of partially injective homomorphisms, Explicit error bounds for lazy reversible Markov chain Monte Carlo, Expanding and forwarding, Boolean approximate counting CSPs with weak conservativity, and implications for ferromagnetic two-spin, Convergence time to equilibrium of the Metropolis dynamics for the GREM, Rates of convergence of some multivariate Markov chains with polynomial eigenfunctions, Sampling Eulerian orientations of triangular lattice graphs, Approximating the permanent via importance sampling with application to the dimer covering problem, A multiscale environment for learning by diffusion, Mixing of permutations by biased transpositions, A discipline of evolutionary programming, Sampling \(k\)-partite graphs with a given degree sequence, A version of Aldous' spectral-gap conjecture for the zero range process, Comparing eigenvalue bounds for Markov chains: When does Poincaré beat Cheeger?, Censored Glauber dynamics for the mean field Ising model, Linking and cutting spanning trees, An analysis of Monte Carlo algorithm for estimating the permanent, Evolving sets, mixing and heat kernel bounds, Uniform generation of spanning regular subgraphs of a dense graph, Latent semantic indexing: A probabilistic analysis, Polynomial time approximation schemes for dense instances of \( \mathcal{NP}\)-hard problems, Approximating the number of monomer-dimer coverings of a lattice., A load balancing strategy for parallel computation of sparse permanents, Computational complexity of loss networks, Relation-algebraic computation of fixed points with applications, GENERALIZED DOMINOES TILING'S MARKOV CHAIN MIXES FAST, The diameter of the uniform spanning tree of dense graphs, Approximately Counting Independent Sets of a Given Size in Bounded-Degree Graphs, Approximating real-rooted and stable polynomials, with combinatorial applications, Sampling Edge Covers in 3-Regular Graphs, Unnamed Item, Mixing of the Glauber dynamics for the ferromagnetic Potts model, Approximating the permanent: A simple approach, A Mildly Exponential Time Algorithm for Approximating the Number of Solutions to a Multidimensional Knapsack Problem, Improved Bounds for Mixing Rates of Markov Chains and Multicommodity Flow, Unnamed Item, Perfect Sampling in Infinite Spin Systems Via Strong Spatial Mixing, A Randomised Approximation Algorithm for Counting the Number of Forests in Dense Graphs, Find Your Place: Simple Distributed Algorithms for Community Detection, Smoothed counting of 0–1 points in polyhedra, Efficient sampling and counting algorithms for the Potts model on ℤ^d at all temperatures, Perfect sampling from spatial mixing, Efficiently list‐edge coloring multigraphs asymptotically optimally, Swendsen-Wang dynamics for the ferromagnetic Ising model with external fields, Algebraic and combinatorial expansion in random simplicial complexes, Sequential importance sampling for estimating expectations over the space of perfect matchings, Spatial mixing and the random‐cluster dynamics on lattices, Low-temperature Ising dynamics with random initializations, Finite-size scaling, phase coexistence, and algorithms for the random cluster model on random graphs, Unnamed Item, Approximate sampling of graphs with near-\(P\)-stable degree intervals, Geometric bounds on the fastest mixing Markov chain, Estimation of spectral gap for Markov chains, Unnamed Item, Polynomial Time Algorithms to Approximate Permanents and Mixed Discriminants Within a Simply Exponential Factor, Some Problems on Approximate Counting in Graphs and Matroids, Unnamed Item, On the Complexity of Holant Problems, Isoperimetry in integer lattices, Uniform sampling ofk-hypertournaments, A semidefinite bound for mixing rates of Markov chains, Monomer-dimer problem on random planar honeycomb lattice, Markov-chain monte carlo: Some practical implications of theoretical results, Counting independent sets in graphs with bounded bipartite pathwidth, Counting over non-planar graphs, Unnamed Item, Unnamed Item, Unnamed Item, Counting without sampling: Asymptotics of the log-partition function for certain statistical physics models, Clifford algebras and approximating the permanent, Gibbs rapidly samples colorings of \(G(n, d/n)\), Graph classes and the switch Markov chain for matchings, On quantitative convergence to quasi-stationarity, Error bounds for computing the expectation by Markov chain Monte Carlo, Approximately Counting Embeddings into Random Graphs, The first two largest eigenvalues of Laplacian, spectral gap problem and Cheeger constant of graphs, An asymptotic approximation for the permanent of a doubly stochastic matrix, Bravely, Moderately: A Common Theme in Four Recent Works, An Almost m-wise Independent Random Permutation of the Cube, Approximability of the eight-vertex model, Conductance bounds on the L² convergence rate of Metropolis algorithms on unbounded state spaces, Counting Perfect Matchings and the Switch Chain, A Polynomial-Time Approximation Algorithm for All-Terminal Network Reliability, ON THE COMPLEXITY OF COUNTING FIXED POINTS AND GARDENS OF EDEN IN SEQUENTIAL DYNAMICAL SYSTEMS ON PLANAR BIPARTITE GRAPHS, Counting Restricted Homomorphisms via Möbius Inversion over Matroid Lattices, Counting Weighted Independent Sets beyond the Permanent, Matrix permanent and quantum entanglement of permutation invariant states, A Decomposition Based Proof for Fast Mixing of a Markov Chain over Balanced Realizations of a Joint Degree Matrix, Spectral Independence in High-Dimensional Expanders and Applications to the Hardcore Model, Rapid Mixing of the Switch Markov Chain for 2-Class Joint Degree Matrices, Generalization of discrete-time geometric bounds to convergence rate of Markov processes on Rⁿ