Approximating the Permanent

DOI10.1137/0218077zbMath0723.05107DBLPjournals/siamcomp/JerrumS89OpenAlexW2106285343WikidataQ56386807 ScholiaQ56386807MaRDI QIDQ3211352

Alistair Sinclair, Mark R. 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

zbMATH Keywords

simulated annealingMarkov chainstatistical physicspermanentrandom generationperfect matchingscounting problems0-1 matrixrapid mixingmonomer-dimer systemrandomised 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 (only showing first 100 items - show all)

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ⁿ ⋮ 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.

This page was built for publication: Approximating the Permanent