Improved Bounds for Mixing Rates of Markov Chains and Multicommodity Flow
From MaRDI portal
Publication:4291194
DOI10.1017/S0963548300000390zbMATH Open0801.90039OpenAlexW2033281046MaRDI QIDQ4291194FDOQ4291194
Publication date: 1 December 1994
Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1017/s0963548300000390
Recommendations
Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Deterministic network models in operations research (90B10)
Cites Work
- Eigenvalues and expanders
- Isoperimetric numbers of graphs
- Geometric bounds for eigenvalues of Markov chains
- Markov chain models - rarity and exponentiality
- Approximate counting, uniform generation and rapidly mixing Markov chains
- Fast uniform generation of regular graphs
- Approximating the Permanent
- The maximum concurrent flow problem
- \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators
- Bounds on the L 2 Spectrum for Markov Chains and Markov Processes: A Generalization of Cheeger's Inequality
- Some Inequalities for Reversible Markov Chains
- Sparsest cuts and bottlenecks in graphs
- On the Markov Chain Simulation Method for Uniform Combinatorial Distributions and Simulated Annealing
Cited In (only showing first 100 items - show all)
- A randomized algorithm for the joining protocol in dynamic distributed networks
- Tight estimates for convergence of some non-stationary consensus algorithms
- The cover times of random walks on random uniform hypergraphs
- Sampling Edge Covers in 3-Regular Graphs
- Dynamics of \((2+1)\)-dimensional SOS surfaces above a wall: slow mixing induced by entropic repulsion
- Randomly coloring planar graphs with fewer colors than the maximum degree
- The mixing time of Glauber dynamics for coloring regular trees
- Sequential stratified regeneration: \textit{MCMC} for large state spaces with an application to subgraph count estimation
- Sensitivity and convergence of uniformly ergodic Markov chains
- Uniform Sampling of Digraphs with a Fixed Degree Sequence
- Slow droplet-driven relaxation of stochastic Ising models in the vicinity of the phase coexistence region
- Large cycles in generalized Johnson graphs
- Blocking Conductance and Mixing in Random Walks
- Tight bounds for the cover time of multiple random walks
- A modified conditional Metropolis-Hastings sampler
- Stochastic modelling of the eukaryotic heat shock response
- A one-dimensional coagulation-fragmentation process with a dynamical phase transition
- On nodal domains and higher-order Cheeger inequalities of finite reversible Markov processes
- Strong Spatial Mixing and Rapid Mixing with Five Colours for the Kagome Lattice
- Spectral gap for the zero range process with constant rate
- The spectral gap of the REM under Metropolis dynamics
- Pattern hit-and-run for sampling efficiently on polytopes
- Approximating the number of monomer-dimer coverings of a lattice.
- Minimising MCMC variance via diffusion limits, with an application to simulated tempering
- NON-BACKTRACKING RANDOM WALKS MIX FASTER
- On the cover time and mixing time of random geometric graphs
- Pattern discrete and mixed hit-and-run for global optimization
- On the two-dimensional dynamical Ising model in the phase coexistence region
- Approximating the number of double cut-and-join scenarios
- Systematic scan for sampling colorings
- A dynamic programming approach to efficient sampling from Boltzmann distributions
- Self-testing algorithms for self-avoiding walks
- Opinion dynamics in social networks with stubborn agents: equilibrium and convergence rate
- Counting and sampling SCJ small parsimony solutions
- A semidefinite bound for mixing rates of Markov chains
- Spectral gap of random hyperbolic graphs and related parameters
- Cover time of a random graph with given degree sequence
- Subset Glauber dynamics on graphs, hypergraphs and matroids of bounded tree-width
- Simple permutations mix even better
- Geometric bounds for convergence rates of averaging algorithms
- Approximate Spectral Gaps for Markov Chain Mixing Times in High Dimensions
- On the rate of convergence of the Gibbs sampler for the 1-D Ising model by geometric bound
- Logarithmic Sobolev, isoperimetry and transport inequalities on graphs
- Markov-chain monte carlo: Some practical implications of theoretical results
- Testing Expansion in Bounded-Degree Graphs
- On approximating weighted sums with exponentially many terms
- Geometric Approaches to the Estimation of the Spectral Gap of Reversible Markov Chains
- Geometric ergodicity of a more efficient conditional Metropolis-Hastings algorithm
- Dimension spectrum of Axiom A diffeomorphisms. I: The Bowen-Margulis measure
- Convergence of Conditional Metropolis-Hastings Samplers
- The cover time of random geometric graphs
- Applications of geometric bounds to the convergence rate of Markov chains on \(\mathbb R^ {n}\).
- Derandomized constructions of \(k\)-wise (almost) independent permutations
- Comparing eigenvalue bounds for Markov chains: When does Poincaré beat Cheeger?
- Clustering and community detection in directed networks: a survey
- Improved bounds for sampling colorings
- Configuring Random Graph Models with Fixed Degree Sequences
- What do we know about the Metropolis algorithm?
- The mixing time of a random walk on a long-range percolation cluster in pre-Sierpinski gasket
- The worm process for the Ising model is rapidly mixing
- Logarithmic Sobolev inequalities for finite Markov chains
- Sampling binary contingency tables with a greedy start
- A new genetic algorithm
- Dobrushin Conditions and Systematic Scan
- Random cluster dynamics for the Ising model is rapidly mixing
- Thermalization time bounds for Pauli stabilizer Hamiltonians
- Poisson approximation for non-backtracking random walks
- Conditions for rapid mixing of parallel and simulated tempering on multimodal distributions
- On mixing and edge expansion properties in randomized broadcasting
- Conductance and noncommutative dynamical systems
- Complexity analysis of Bayesian learning of high-dimensional DAG models and their equivalence classes
- Switch-based Markov chains for sampling Hamiltonian cycles in dense graphs
- Structure and eigenvalues of heat-bath Markov chains
- An Almost m-wise Independent Random Permutation of the Cube
- Some rapidly mixing hit-and-run samplers for latent counts in linear inverse problems
- Scale-free percolation mixing time
- The Glauber dynamics for edge‐colorings of trees
- Linking and cutting spanning trees
- Intersection Conductance and Canonical Alternating Paths: Methods for General Finite Markov Chains
- Swendsen-Wang dynamics for the ferromagnetic Ising model with external fields
- Mixing of the square plaquette model on a critical length scale
- Markov chain convergence: From finite to infinite
- Regularized modified log-Sobolev inequalities and comparison of Markov chains
- Title not available (Why is that?)
- The mixing time of switch Markov chains: a unified approach
- Mixing of Markov chains for independent sets on chordal graphs with bounded separators
- Title not available (Why is that?)
- Title not available (Why is that?)
- Comparing with octopi
- Polynomial-time approximation algorithms for the antiferromagnetic Ising model on line graphs
- Grid spanners with low forwarding index for energy efficient networks
- The Quantum Complexity of Markov Chain Monte Carlo
- Approximability of the eight-vertex model
- Title not available (Why is that?)
- Rapid Mixing of the Switch Markov Chain for 2-Class Joint Degree Matrices
- Title not available (Why is that?)
- Approximate sampling of graphs with near-\(P\)-stable degree intervals
- Mixing time of the swap Markov chain and \(P\)-stability
- Half-graphs, other non-stable degree sequences, and the switch Markov chain
- Some Problems on Approximate Counting in Graphs and Matroids
This page was built for publication: Improved Bounds for Mixing Rates of Markov Chains and Multicommodity Flow
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4291194)
