An approximation algorithm for counting contingency tables
From MaRDI portal
Publication:3057067
DOI10.1002/rsa.20301zbMath1208.68235arXiv0803.3948OpenAlexW3083208292MaRDI QIDQ3057067
Zur Luria, Alex Samorodnitsky, Alexander Yong, Alexander I. Barvinok
Publication date: 24 November 2010
Published in: Random Structures & Algorithms (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/0803.3948
Analysis of algorithms and problem complexity (68Q25) Monte Carlo methods (65C05) Contingency tables (62H17) Approximation algorithms (68W25) Randomized algorithms (68W20)
Related Items
On the mixing time of the Diaconis-Gangolli random walk on contingency tables over \(\mathbb{Z}/q\mathbb{Z} \), Lower bounds for contingency tables via Lorentzian polynomials, On testing Hamiltonicity of graphs, Phase transition in random contingency tables with non-uniform margins, Majorization and the number of bipartite graphs for given vertex degrees, An asymptotic formula for the number of non-negative integer matrices with prescribed row and column sums, Random sampling of contingency tables via probabilistic divide-and-conquer, Fibers of multi-way contingency tables given conditionals: relation to marginals, cell bounds and Markov bases
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The Van der Waerden conjecture for mixed discriminants
- Brunn--Minkowski inequalities for contingency tables and integer flows
- Asymptotic enumeration of sparse nonnegative integer matrices with specified row and column sums
- Van der Waerden/Schrijver-Valiant like conjectures and stable (aka hyperbolic) homogeneous polynomials: one theorem for all
- Testing for independence in a two-way table: New interpretations of the chi-square statistic
- Proof of the van der Waerden conjecture regarding the permanent of a doubly stochastic matrix
- The solution of van der Waerden's problem for permanents
- The asymptotic number of non-negative integer matrices with given row and column sums
- On the application of symmetric Dirichlet distributions and their mixtures to contingency tables
- A lower bound for the permanent of a doubly stochastic matrix
- Log-Sobolev inequalities and sampling from log-concave distributions
- Sampling from log-concave distributions
- Counting integer flows in networks
- On the complexity of nonnegative-matrix scaling
- Scaling of matrices to achieve specified row and column sums
- A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries
- Rapidly Mixing Markov Chains for Sampling Contingency Tables with a Constant Number of Rows
- Asymptotic Estimates for the Number of Contingency Tables, Integer Flows, and Volumes of Transportation Polytopes
- New permanental upper bounds for nonnegative matrices
- Improved bounds for sampling contingency tables
- A Relationship Between Arbitrary Positive Matrices and Doubly Stochastic Matrices
- Enumerating Contingency Tables via Random Permanents
- Sequential Monte Carlo Methods for Statistical Analysis of Tables
- A polynomial-time algorithm to approximately count contingency tables when the number of rows is constant
- A deterministic strongly polynomial algorithm for matrix scaling and approximate permanents
