Sampling binary contingency tables with a greedy start

DOI10.1002/RSA.20155MaRDI QIDQ5898351zbMATH OpenOpenAlexFDO

Authors Ivona Bezáková, Nayantara Bhatnagar, Eric Vigoda

Publication date 7 February 2007

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1002/rsa.20155

zbMATH Keywords

bootstrappinggreedy graph

Mathematics Subject Classification ID

Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.) (60J20) Contingency tables (62H17) Approximation methods and heuristics in mathematical programming (90C59)

Recommendations

• Sampling contingency tables
• scientific article; zbMATH DE number 1223716
• Improved bounds for sampling contingency tables
• Rapidly Mixing Markov Chains for Sampling Contingency Tables with a Constant Number of Rows
• An approximation algorithm for counting contingency tables

Cites work

• A theorem on flows in networks
• Accelerating simulated annealing for the permanent and combinatorial counting problems
• Generating random regular graphs
• scientific article; zbMATH DE number 795108 (Why is no real title available?)
• scientific article; zbMATH DE number 6472593 (Why is no real title available?)
• Improved Bounds for Mixing Rates of Markov Chains and Multicommodity Flow
• Monte Carlo strategies in scientific computing
• Sampling regular graphs and a peer-to-peer network

Cited in

(20)

• Sampling hypergraphs with given degrees
• On the mixing time of the Diaconis-Gangolli random walk on contingency tables over \(\mathbb{Z}/q\mathbb{Z} \)
• A fast MCMC algorithm for the uniform sampling of binary matrices with fixed margins
• The mixing time of switch Markov chains: a unified approach
• Efficient importance sampling for binary contingency tables
• Monte Carlo algorithms for computing \(\alpha \)-permanents
• Uniform sampling of digraphs with a fixed degree sequence
• Sampling contingency tables
• New classes of degree sequences with fast mixing swap Markov chain sampling
• Improved bounds for sampling contingency tables
• Characterizing optimal sampling of binary contingency tables via the configuration model
• A Decomposition Based Proof for Fast Mixing of a Markov Chain over Balanced Realizations of a Joint Degree Matrix
• On the Diaconis-Gangolli Markov Chain for Sampling Contingency Tables with Cell-Bounded Entries
• Approximately counting embeddings into random graphs
• A polynomial-time algorithm to approximately count contingency tables when the number of rows is constant
• On the Diaconis-Gangolli Markov chain for sampling contingency tables with cell-bounded entries
• Approximate sampling and counting of graphs with near-regular degree intervals
• Random sampling of contingency tables via probabilistic divide-and-conquer
• On the number of matrices and a random matrix with prescribed row and column sums and 0-1 entries
• An efficient MCMC algorithm to sample binary matrices with fixed marginals

This page was built for publication: Sampling binary contingency tables with a greedy start

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5898351)